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; } }