题号：P1032
不是特好写，用了Map。除此之外他题里面有一点没说清楚，也就是替换字符串的时候每个字符串不同位置各替换一次，示例：
Original String:”baaba”
Map:”a”=>”b”
Generated String:{“bbaba”,”babba”,”baabb”}
就是这样。代码如下：
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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<queue> #include<map> #include<functional> using namespace std; string A, B; int n = 1; string p[10][2]; queue<string> qs; queue<int> qn; map<string, bool> dic; inline string replace(const string& origin, const string& toreplace, const string& replacement,int time) { string s = origin; int curpos = 0; time--; while (s.find(toreplace, curpos) != string::npos&&time) { curpos = s.find(toreplace, curpos)+toreplace.length(); time--; } if (s.find(toreplace, curpos) != string::npos) { s.replace(s.find(toreplace, curpos), toreplace.length(), replacement); return s; } return ""; } int main() { cin >> A >> B; while (cin >> p[n][0] >> p[n][1])n++; qs.push(A); qn.push(0); while (!qs.empty()) { string s = qs.front(); int time = qn.front(); qs.pop(); qn.pop(); if (dic.count(s) || time > 10)continue; dic[s] = true; if (s == B) { cout << time; return 0; } for (int i = 1; i < n; i++) { string s2; for (int j = 1;; j++) { s2= replace(s, p[i][0], p[i][1],j); if (s2 == "")break; if (!dic.count(s2) && time + 1 <= 10) { qs.push(s2); qn.push(time + 1); } } } } cout << "NO ANSWER!"; } |