题目描述
题目大意
- 从字符串A到字符串B需要至少经过几次替换
解题思路
- 双向广搜：从两个方向同时搜索，而不是从一个方向搜到另一个方向
- 每次每一边只扩展一个点是不正确的，正确做法应该是每次每边扩展完整一层
题目代码
#include
#include
#include
#include
#include
using namespace std;
const int N = 6;
int n;
string A, B;
string a[N], b[N];
int extend(queue& q, unordered_map&da, unordered_map& db,
string a[N], string b[N])
{
int d = da[q.front()];
while (q.size() && da[q.front()] == d)
{
auto t = q.front();
q.pop();
for (int i = 0; i < n; i ++ )
for (int j = 0; j < t.size(); j ++ )
if (t.substr(j, a[i].size()) == a[i])
{
string r = t.substr(0, j) + b[i] + t.substr(j + a[i].size());
if (db.count(r)) return da[t] + db[r] + 1;
if (da.count(r)) continue;
da[r] = da[t] + 1;
q.push(r);
}
}
return 11;
}
int bfs()
{
if(A == B) return 0;
queue qa, qb;
unordered_map da, db;
qa.push(A), qb.push(B);
da[A] = db[B] = 0;
//int step = 0;
while(qa.size() && qb.size())
{
int t;
if(qa.size() < qb.size()) t = extend(qa, da, db, a, b);
else t = extend(qb, db, da, b, a);
if(t > A >> B;
while(cin >> a[n] >> b[n]) n ++;
int t = bfs();
if(t == -1) puts("NO ANSWER!");
else cout << t << endl;
return 0;
}
Original: https://www.cnblogs.com/esico/p/16478082.html
Author: esico
Title: AcWing 190. 字串变换（搜索）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/619907/
转载文章受原作者版权保护。转载请注明原作者出处！