二刷提高课,题解目录在这里— 提高课的题解目录
此题又引入了一个解决问题的思想,双向广搜
当我们从一个方向搜索结果时间复杂度过于高时,可以试用双向广搜
原理就是用空间换时间,记录两边搜索到的结果看是否有重合
还有一点就是我们搜索的时候一定要搜索一层而不是一个(和我们bfs操作类似)每次搜一层
可以大大减小时间消耗(记住这种解决问题的思想)
#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
const int N=6;
int n;
string sta,en;
string a[N],b[N];
int solve(queue<string>&q,unordered_map<string,int>&da,unordered_map<string,int>&db, string a[N], string b[N])
{
//注意这里要遍历一层,而一层的共同点就是遍历的次数da
int d=da[q.front()];
while(q.size()&&d==da[q.front()])
{
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 tt=t.substr(0,j)+b[i]+t.substr(j+a[i].size());
if(db.count(tt))return da[t]+db[tt]+1;
if(da.count(tt))continue;
da[tt]=da[t]+1;
q.push(tt);
}
}
}
}
return 11;
}
int bfs()
{
if(sta==en)return 0;
queue<string >qa,qb;
unordered_map<string ,int >da,db;
qa.push(sta);
qb.push(en);
da[sta]=db[en]=0;
int step=0;
while(qa.size()&&qb.size())//优化:每次选择剩余最小的来使得搜索平衡一些
{
int t;
if(qa.size()<qb.size())t=solve(qa,da,db,a,b);
else t=solve(qb,db,da,b,a);
if(t<=10)return t;
if(++step==10)return -1;
}
return -1;
}
int main()
{
cin>>sta>>en;
while(cin>>a[n]>>b[n])n++;
int t=bfs();
if(t==-1)cout<<"NO ANSWER!";
else cout<<t;
return 0;
}