80分,WA#5,求助
查看原帖
80分,WA#5,求助
1185696
afreshmanofclanguage楼主2024/9/1 20:13

这是80分的代码:

#include<bits/stdc++.h>
using namespace std;
string a, b, ai, bi;
int idx, pos;
typedef pair<string, int> PSI;
typedef pair<string, string> PSS;
PSS cha[100];
queue<PSI>q;
int bfs(string st)
{
    q.push({ st,0 });
    while (q.size())
    {
        auto t = q.front().first; // 某一个状态的字符串
        int dep = q.front().second; // 某一个状态的层数
        if (dep > 10) return -1;
        q.pop();
        for (int i = 1; i <= idx; i++)
        {
            string tem = t;
            int pos = -1;
            string ai = cha[i].first;
            string bi = cha[i].second;
            while ((pos = tem.find(ai.c_str())) != -1)
            {
                tem.replace(pos, ai.size(), bi.c_str());
                if (tem == b) return dep + 1;
                q.push({ tem,dep + 1 });
            }
        }
    }
    return -1;
}
int main()
{
    cin >> a >> b;
    while (cin >> ai >> bi)
        cha[++idx] = { ai,bi }; //绑定
    if (a == b)
    {
        printf("0");
        return 0;
    }
    int ans = bfs(a);
    if (ans == -1) printf("NO ANSWER!");
    else cout << ans;
    return 0;
}
2024/9/1 20:13
加载中...