帮你改了一下bfs代码
```cpp
#include <stdio.h>
#include <queue>
#include <string>
#include <iostream>
using namespace std;
string a[200], b[200], s, f;
int i, ans = 1e9;
struct node
{
string s;
int ti; // 变换次数
};
queue<node> q;
int main(void)
{
int j;
cin >> s >> f;
for (i = 0; cin >> a[i] >> b[i]; i++)
;
q.push((node){s, 0});
node tmp;
string news;
while (!q.empty())
{
tmp = q.front();
q.pop(); // 出队
string so = tmp.s;
int nowti = tmp.ti + 1; // 本次的新替换次数
if (nowti > 10)
continue;
for (j = 0; j < i; j++)
{ // 枚举所有的替换规则
int loc = so.find(a[j]);
int le = a[j].length();
if (loc == -1)
continue;
do
{
news = so;
news.replace(loc, le, b[j]);
if (news == f)
{
cout << nowti;//此处修正,广搜嘛,第一次搜到就是最优解
exit(0);
}
else
{
q.push((node){news, nowti}); // 次数小于10的才进队!
}
loc = so.find(a[j], loc + 1); // 从后一个位置再次查找,直到查找不到
} while (loc != -1);
}
}
ans > 10 ? printf("NO ANSWER!") : printf("%d", ans);
return 0;
}
``````
by carboxylBase @ 2024-04-02 15:02:47
可以用启发式搜索排除不可能的情况,这样可以避免队列的高空间
by 2308weibowen @ 2024-05-12 14:00:43