如下代码,注释起来的是满分代码,没注释的是90分版本。到底是为啥呀,感觉两种读入方式没区别呀。
#include <iostream>
#include <cstring>
#include <queue>
#include <unordered_map>
using namespace std;
// typedef pair<string, string> pss;
unordered_map<string, string> h;
unordered_map<string, int> vis;
int n = 1;
string a, b;
// pss h[10];
struct Node {
string s;
int c;
};
int bfs() {
queue<struct Node> q;
q.push({a, 0});
vis[a] = 1;
while(!q.empty()) {
auto t = q.front();
q.pop();
if(t.c > 10) return -1;
// for(int i = 1; i <= n; i ++) {
for(auto i : h) {
// int pos = t.s.find(h[i].first, 0);
int pos = t.s.find(i.first, 0);
while(pos != -1) {
string tmp = t.s;
// 用i.second替换从pos开始长度为i.first.size()的字符串,注意返回到tmp
// tmp.replace(pos, h[i].first.size(), h[i].second);
tmp.replace(pos, i.first.size(), i.second);
if(tmp == b) {
return t.c + 1;
}
if(!vis[tmp]) {
q.push({tmp, t.c + 1});
vis[tmp] = 1;
}
// pos = t.s.find(h[i].first, pos + 1);
pos = t.s.find(i.first, pos + 1);
}
}
}
return -1;
}
int main() {
cin >> a >> b;
if(a == b) {
cout << 0 << endl;
return 0;
}
// while(cin >> h[n].first >> h[n].second) {
// n ++;
// }
// n --;
string tmpa, tmpb;
while(cin >> tmpa >> tmpb) { // 为什么这种读入 第一个测试点会过不了????
h[tmpa] = tmpb;
}
int res = bfs();
if(res != -1) cout << res << endl;
else puts("NO ANSWER!");
return 0;
}