字串变换
双端队列的整体框架:
- 首先处理读入输出
- bfs函数里定义好所需距离函数和队列,并且只要有一个队列不空,就继续循环,每次循环判断那一边队列的元素少就先扩展哪一边
- 拓展时每次拓展一层
详细的说明见代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
const int N=6;
int n;//变换数
string A,B;//初始状态和最终状态
string a[N],b[N];//变换的前后状态
int extend(queue<string> &q, unordered_map<string,int> &da,
//待扩展的队列和当前队列对应的距离函数
unordered_map<string,int> &db,string a[], string b[])
//另一队列的距离函数,变换的前后状态
{
int d=da[q.front()];//提取当前队列的队头元素的的距离
while(q.size()&&da[q.front()]==d){//拓展一层元素
string 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;
//把新状态r的距离更新
q.push(r);
//新状态入队
}
}
}
}
return 11;//返回任意不合法的情况
}
int bfs(){
if(A==B)return 0;
unordered_map<string,int> da,db;//两个队列的距离函数
queue<string> qa,qb;//两个队列
qa.push(A),qb.push(B);//A和B入队
da[A]=db[B]=0;//A和B的距离设置为0
int step=0;//步数
while(qa.size()&&qb.size()){//只要有一个队列空了还没找到对方,说明无解
int t;
if(qa.size()>qb.size())t=extend(qb,db,da,b,a);
//若b队列元素小于a,则拓展b
else t=extend(qa,da,db,a,b);
//否则拓展a
if(t<=10) return t;
//若步数合法,则返回步数
if(++step==10)return -1;
//步数大于10,则非法
}
return -1;
}
int main(){
cin>>A>>B;
while(cin>>a[n]>>b[n])n++;
int t=bfs();
if(t==-1)puts("NO ANSWER!");
else cout<<t;
return 0;
}