Problem 1296 : Repeated Substitution with Sed

Problem B: Repeated Substitution with Sed
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1296

• 問題概要

与えられた複数法則で文字列を置き換える。
その法則を適応できるだけ適応する。
一個だけ適応とか、置き換える部分がかぶるのはだめ。
ひとつの法則を適応することに一回変換したと数える。
最初の文字から目標の文字列に変換するまで、何回変換すればたどり着けますか。
変換前の文字列より変換後の文字列の方が長いことが保証されている。

• 解法

全探索。
変換後の方が長くなるので、目標の文字列の文字数をこえた時点で枝刈り。
なのでふかさはあまりふかくならない。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;

map<string, string> index;
set<string> used;
string end;
int ans;
void DFS(int cost, string s){
  if( s == end){
    ans = min(ans, cost);
    return;
  }
  FOR(it, index){
    string tmp =(*it).first, to = (*it).second;
    int l = tmp.length();
    string next="";
    for(int i=0; i<s.length(); i++){
      if(i+l-1 < s.length() && s.substr(i, l) == tmp){ 
	next += to;
	i+=l-1;
      }
      else next +=s[i];
    }
    if(s == next || next.length() > end.length())continue;
    DFS(cost+1, next);
  }
}


main(){
  int n;
  while(cin >> n){
    if(n == 0)break;
    index.clear();
    used.clear();
    rep(i, n){
      string tmp1, tmp2;
      cin >> tmp1 >> tmp2;
      index[tmp1] = tmp2;
    }
    string s;
    cin >> s >> end;
    ans = 999999;
    DFS(0, s);
    if(ans > 100000)ans = -1;
    cout << ans << endl;
  }
}

問題読み違えてかなりつまった。
ちゃんと読んでから解きましょう。