AOJ 1296: Repeated Substitution with Sed

メモ化の大切さを感じた。問題はこちら。

問題

文字（列）の置換ペアをいくつか与えられる。スタート文字列とゴール文字列も与えられる。スタート文字列を与えられた文字列置換ペアよってゴール文字列へと変換することができるか、できるのであれば必要な置換の最小回数を答える。

解法

幅優先探索で解く。スタート文字列から出発し、各ペアによる置換を試していけばいい。置換後にゴール文字列の長さを超えたものはパスする。メモ化をきちんとして、一度調べた文字列をパスしないようにしないとTLEとなってしまう（一度やってしまった）。重複をなくすという競プロでは重要な工夫に対する意識がまだ十分でないので、しっかりと意識していきたい。

while 1:
    n = int(raw_input())
    if n == 0: break
    ab = [raw_input().split() for i in xrange(n)]
    s = raw_input()
    g = raw_input()
    memo = set([s])
    que = [[s,0]]
    while que:
        c,i = que.pop(0)
        if c == g:
            print i
            break
        for a,b in ab:
            cc = c.replace(a,b)
            if len(cc) > len(g) or cc in memo: continue
            memo.add(cc)
            que.append([cc,i+1])
    else:
        print -1