“
很明显是最小步数模型,我们先来分析一波单向起点开始bfs需要的空间:
假设每次决策数量是 K,那么如果直接BFS,最坏情况下的搜索空间是 K^10,非常大,所以会TLE或者MLE。第一层是1,第二层是K,第三层是K*K=K^2…..K^10
如果采用双向BFS,则可以把搜索空间降到 2K^5。在实际测试中只需 20ms 左右,剪枝效果很好。
BFS的扩展方式是:分别枚举在原字符串中使用替换规则的起点,和所使用的的替换规则。
双向bfs的一个小优化:在双向BFS时,每次选择队列中元素数量较少的方向来扩展。
”
总结:
·一边扩展完了另一边还能扩展,说明不连通,达不到终状态
·在枚举能替换的状态的时候用substr函数可以方便很多
·写代码的时候压入队列扩展写一份即可,从起点扩展的方式和从终点扩展的方式是反过来的,一个是a变化到b,一个是变化 到a.
题目描述
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<unordered_map>
using namespace std;
const int N=6;
string a[N],b[N];
int n;
int extend(queue<string>& q,unordered_map<string,int>& da,unordered_map<string,int>& db,string a[],string b[])
{
auto t=q.front();
q.pop();
for(int i=0;i<t.size();i++)
for(int j=0;j<n;j++)
{
if(t.substr(i,a[j].size())==a[j])
{
string str=t.substr(0,i)+b[j]+t.substr(i+a[j].size());
if(db.count(str)) return da[t]+1+db[str];
if(da.count(str)) continue;
da[str]=da[t]+1;
q.push(str);
}
}
return -1;
}
int bfs(string A,string B)
{
queue<string>qa,qb;
unordered_map<string,int>da,db;
qa.push(A);qb.push(B);
da[A]=0;db[B]=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!=-1) return t;
}
return 11;
}
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
string A,B;
cin>>A>>B;
n=0;
while(cin>>a[n]>>b[n]) n++;
int step=bfs(A,B);
if(step<=10) cout<<step<<endl;
else cout<<"NO ANSWER!"<<endl;
return 0;
}
超时了