1296-Repeated Substitution with Sed

問題概要

文字列A(10文字以下)を置換を用いて文字列B(10文字以下)に変換するときの最小の置換回数を求めよ．
ただし置換は左側から重複しないように行なわれる．
またこの置換によって文字数が減ることや変わらないということは起こらない．

考え方

最小なのでBFSでも良いが，置換回数はたかだか9回なので実装が楽なDFSを用いた．

実装(C++)

#include <vector>
#include <map>
#include <iostream>
using namespace std;



typedef pair<string,string> P;
string start;
string end;
int n;
int ans;
vector<P> convert;
string replace(const string &in,int no){
	string next;
	int n=in.size();
	for(int i=0;i<n;i++){
		if(i<=n-(int)convert[no].first.size()&&in.substr(i,(int)convert[no].first.size())==convert[no].first){
			next+=convert[no].second;
			i+=convert[no].first.size()-1;
		}else{
			next+=in[i];
		}
	}
	return next;
}
//DFS
void dfs(string in,int v){
	if(in==end){
		ans=min<int>(ans,v);
		return;
	}
	if(in.size()>=end.size())return;
	if(v>=ans)return;
	if(v>=10)return;
	for(int i=0;i<n;i++){
		string next=replace(in,i);
		if(next!=in)dfs(next,v+1);
	}
}

int main() {
	for(;cin>>n;){
		if(!n)break;
		convert=vector<P>(n);
		ans=9999;
		for(int i=0;i<n;i++){
			cin>>convert[i].first>>convert[i].second;
		}
		cin>>start>>end;
		dfs(start,0);
		if(ans==9999)ans=-1;
		cout<<ans<<endl;
	}
	return 0;
}