POJ 3803 - Repeated Substitution with Sed

http://poj.org/problem?id=3803

概要

n 種類の置換 α -> β と，もととなる文字列 γ，最終的な文字列 δ が与えられる．

n 種類の置換をうまく使って，γ を δ にするのに必要な最小の置換回数を答える． ただし，δにすることができないときは -1 を答える．

同じ置換を何度使っても構わない．

制約

• 1 <= |α| < |β| <= 10
• n <= 10
• 1 <= |γ| < |δ| <= 10
• 文字列は小文字のアルファベットのみからなる

解法

置換すると必ず文字列は長くなり，しかも最終的な文字列の長さが10と非常に小さいので適当に深さ優先で全探索すればいい．

 1 #include <iostream>
 2 #include <vector>
 3 #include <set>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 string gsub(string str, const string& pat, const string& sub)
 8 {
 9   for (string::size_type i = 0; i < str.size();) {
10     const string::size_type p = str.find(pat, i);
11     if (p == string::npos) {
12       break;
13     }
14     str.replace(p, pat.size(), sub);
15     i = p + sub.size();
16   }
17   return str;
18 }
19 
20 set<string> visited;
21 vector<pair<string,string> > subs;
22 string target;
23 int ans;
24 void dfs(const string& str, int depth)
25 {
26   if (str == target) {
27     ans = min(ans, depth);
28     return;
29   }
30   if (str.size() >= target.size() || visited.count(str)) {
31     return;
32   }
33   visited.insert(str);
34   for (vector<pair<string,string> >::const_iterator it = subs.begin(); it != subs.end(); ++it) {
35     dfs(gsub(str, it->first, it->second), depth+1);
36   }
37 }
38 
39 int main()
40 {
41   int N;
42   while (cin >> N && N != 0) {
43     subs.resize(N);
44     for (int i = 0; i < N; i++) {
45       cin >> subs[i].first >> subs[i].second;
46     }
47     string str;
48     cin >> str >> target;
49 
50     static const int INF = 10000;
51     visited.clear();
52     ans = INF;
53     dfs(str, 0);
54     cout << (ans == INF ? -1 : ans) << endl;
55   }
56   return 0;
57 }