关于《字串变换》读入问题
  • 板块学术版
  • 楼主cloudyyyyy
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/3/24 16:53
  • 上次更新2023/10/28 05:47:56
查看原帖
关于《字串变换》读入问题
693857
cloudyyyyy楼主2022/3/24 16:53

如下代码,注释起来的是满分代码,没注释的是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;
}
2022/3/24 16:53
加载中...