1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| #include <bits/stdc++.h> #define rint register int using namespace std; int main() { string A, B, a[10], b[10], ta, tb; int tot; cin >> A >> B; while (cin >> ta >> tb) { a[tot] = ta; b[tot++] = tb; } queue<pair<string, int> > que; que.push(make_pair(A, 0)); set<pair<string, int> > st; st.insert(make_pair(A, 0)); while (!que.empty()) { pair<string, int> s = que.front(); que.pop(); if (s.first == B) { cout << s.second; return 0; } if (s.second == 10) continue; for (rint i = 0; i<tot; ++i) { string::size_type pos = 0; while ((pos = s.first.find(a[i], pos)) != string::npos) { string ss = s.first; ss.replace(pos, a[i].size(), b[i]); pair<string, int> p = make_pair(ss, s.second + 1); if (st.find(p) == st.end()) { st.insert(p); que.push(p); } pos += a[i].size(); if (pos >= s.first.size()) break; } } } cout << "NO ANSWER!"; return 0; }
|