BFS

听上去蛮简单的,实际编程复杂度较高(至少一个快睡着的人是这么认为的...)

抄的题解(感谢题解的作者<'_'>):

#include<queue>
#include<iostream>
#include<string>
#include<set>
using namespace std; struct node
{
int step;
string s;
node(int step=,string s=""):step(step),s(s){}
};
set<string>c;
queue<node>q;
string st,end,a[],b[];
int n=,ans=-; int main()
{
cin>>st>>end;
node start(,st);
q.push(start);
c.insert(start.s); while(cin>>a[n]>>b[n])n++;
n--; while(!q.empty())
{
node ing=q.front();
q.pop();
if(ing.s==end&&ing.step<=)
{
ans=ing.step;
break;
}
if(ing.step>)break;
for(int i=;i<=n;i++)
{
for(int j=;j<ing.s.length();j++)
{
int v=ing.s.find(a[i],j);
if(v>=)
{
node in=ing;
in.s.replace(v,a[i].length(),b[i]);
in.step++;
if(!c.count(in.s))
{
q.push(in);
c.insert(in.s);
}
}
}
}
} if(ans!=-)cout<<ans;
else cout<<"NO ANSWER!"; return ;
}
05-11 07:31
查看更多