题目描述
已知有两个字串 A, B 及一组字串变换的规则(至多6个规则):
A1 -> B1
A2 -> B2
…
规则的含义为:在 A 中的子串 A1 可以变换为 B1、A2 可以变换为 B2 …。
例如:A=’abcd’ B=’xyz’
变换规则为:
‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’
则此时,A 可以经过一系列的变换变为 B,其变换的过程为:
‘abcd’->‘xud’->‘xy’->‘xyz’
共进行了三次变换,使得 A 变换为B。
输入格式
输入格式如下:
A B
A1 B1 \
A2 B2 |-> 变换规则
… … /
所有字符串长度的上限为 20。
输出格式
若在 10 步(包含 10步)以内能将 A 变换为 B ,则输出最少的变换步数;否则输出”NO ANSWER!”
样例
输入样例:
abcd xyz
abc xu
ud y
y yz
输出样例:
3
双向BFS
思路
这道题一看也是最小步数模型,所以思考用BFS.
但是如果纯BFS那么20*6,到了后面几层,每一个所拓展到的状态将会很大.时间复杂度无法承受
那么我们可以考虑双向BFS.
一个小小优化:为了均衡两个方向的大小,会用点数量更少的去拓展.
注意次拓展的是每一层,从上一层的点全部拓展到下一层.而不是一个点拓展到下一层的部分点.证明见 yxc
如果拓展到某一个方向的队列为空但是另一个队列还有,那么就说明不连通.
C++ 代码
#include<iostream>
#include<cstring>
#include<queue>
#include<unordered_map>
using namespace std;
int n;
string a[6],b[6];
unordered_map<string,int> dist1;
unordered_map<string,int> dist2;
int bfs(string start,string end)
{
queue<string> q1;
queue<string> q2;
q1.push(start);
q2.push(end);
dist1[start]=0;
dist2[end]=0;
while(!q1.empty()&&!q2.empty())
{
if(q1.size()<=q2.size())
{
int m=q1.size();
while(m--)
{
string t=q1.front();
q1.pop();
for(int i=0;i<(int)t.size();i++)
{
for(int j=0;j<n;j++)
{
if(t.substr(i,a[j].size())==a[j])
{
string state=t.substr(0,i)+b[j]+t.substr(i+a[j].size());
if(!dist1.count(state))
{
if(dist2.count(state))return dist1[t]+dist2[state]+1;
dist1[state]=dist1[t]+1;
q1.push(state);
}
}
}
}
}
}
else{
int m=q2.size();
while(m--)
{
string t=q2.front();
q2.pop();
for(int i=0;i<t.size();i++)
{
for(int j=0;j<n;j++)
{
if(t.substr(i,b[j].size())==b[j])
{
string state=t.substr(0,i)+a[j]+t.substr(i+b[j].size());
if(!dist2.count(state))
{
dist2[state]=dist2[t]+1;
q2.push(state);
if(dist1.count(state))return dist1[state]+dist2[t]+1;
}
}
}
}
}
}
}
return 11;
}
int main()
{
string s,end;
cin>>s>>end;
while(cin>>a[n]>>b[n]) n++;
int step=bfs(s,end);
if(step>10) cout<<"NO ANSWER!";
else cout<<step;
}