1296 Repeated Substitution with Sed

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1296

方針

置換えを実行すると必ず文字数が増えるという条件と、
targetとなる文字列の長さが10以下という条件から、置き換えは最大9回しか起こらないということが分かるので、BFSする。

ソース

#include<iostream>
#include<string>
#include<queue>
#include<map>
#include<set>
using namespace std;

string target,start;
map<string,string> pattern;
set<string> app;

string replaceAll(string s,string f,string t){
  string r;
  for(int pos=0; (pos = s.find(f)) != s.npos; ){
    r+=s.substr(0,pos)+t;
    s = s.substr( pos+f.size() );
  }
  return r+s ;
}

int bfs() {
    queue<pair<string, int> > Q;
    Q.push(make_pair(start,0));
    while(!Q.empty()) {
        string now = Q.front().first;
        int turn = Q.front().second;
        Q.pop();
        if(now.length() > target.length()) continue;
        if(app.find(now) != app.end()) continue;
        app.insert(now);
        if(now == target) return turn;
        for(map<string,string>::iterator it = pattern.begin();
            it != pattern.end(); ++it) {
            string nn = replaceAll(now, (*it).first, (*it).second);
            Q.push(make_pair(nn,turn+1));
        }
    }
    return -1;
}

int main() {
    int n;
    string s,t;
    while(cin>>n, n) {
        pattern.clear();
        app.clear();
        for(int i=0; i<n; ++i) {
            cin>>s>>t;
            pattern[s] = t;
        }
        cin>>start;
        cin>>target;
        cout<<bfs()<<endl;
    }
}