#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
/**
* 这道题的大意就是将A字符串通过一定的规则转变为B字符串
* 一个朴素的思想就是,把A字符串的所有能转变规则的地方都转变一次
* 就相当于从A字符串拓展出几条不同的通路来到达一个新的节点,然后依次类推
* 最后与B字符串连接,这样的问题其实还是一个最短路的问题
* 但是从题目可以看出字符串长度的上限为20,规则至多为6,且步数最多为10步
* 那么我们这样暴力的一层一层BFS,每个节点都要被搜到
* 那么假设每个规则都不重复,那么每个节点都有可能拓展出6条可能的方向来
* 那么最多遍历的点为6^10 = 60,466,176 ≈ 6*10^7
* 如果规则还能重复,比如a -> b,a -> c,那么最多需要遍历(20*6)^10 = 120^10这样时间复杂度就更大了
* --------------------------------------------------------------------------------
* 所以对于这种时间复杂度很大的最短路的问题,我们需要逆向思考
* 因为单独从起点开始去寻找终点,这样可能的分支太多了
* 如果我们起点和终点同时开始去拓展呢,假设10步以内就能找到的话
* 从起点开始拓展5层,从终点开始拓展5层的时候就能够相遇,这个时候的时间复杂度为2*6^5
* 时间复杂度就大为减少了
*/
const int N = 7;
string A,B;//A为起始字符串,B为终点字符串
string a[N],b[N];//a数组和b数组分别存放规则 a -> b
unordered_map<string,int>qa,qb;//qa存放到结点到起点的距离,qb存放该结点到终点的距离
queue<string>q1,q2;//q1和q2分别存放起点和终点拓展的点
int n = 0;
//v代表拓展的队列,a[]和b[]代表规则从a数组->b数组
//这里的qa和qb与我们定义的不同
//如果v对应的是起点拓展的队列,那么qa对应到起点的距离,qb对应到终点的距离
//如果v对应的是终点拓展的队列,那么qa对应到终点的距离,qb对应到起点的距离
//其实也就是从终点开始拓展,那么终点对应终点所拓展的点就相当于起点了
int extend(queue<string>& v,unordered_map<string,int>&qa,unordered_map<string,int>&qb,string a[],string b[])
{
string t = v.front();//从队头弹出一个元素进行拓展
v.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])//如果t字符串中有能与规则相匹配的字符段
{
//把旧字符串中的字符段换成新的字符段重新拼接
string newt = t.substr(0,i) + b[j] + t.substr(i+a[j].size());
//如果新拓展的点到终点存在距离,说明之前已经被终点拓展过
//这个时候起点到终点的距离就为
//弹出那个元素到起点的距离qa[t]
//该元素根据规则换到新的字符串的距离 1
//以及新字符串已经被终点所拓展的距离qb[newt]
if(qb.count(newt)) return qa[t] + 1 + qb[newt];
if(qa.count(newt)) continue;//如果a中已经存在新字符段了就直接continue
v.push(newt);
qa[newt] = qa[t] + 1;//否则就插入新的字符串,并更新新字符串到起点的距离
}
}
}
return 11;
}
int bfs(string A,string B)
{
if(A == B) return 0;
int t;//记录最小步数
qa[A] = 0,qb[B] = 0;//起点和终点的距离分别设置为0
q1.push(A),q2.push(B);
while(q1.size() && q2.size())//只有当q1和q2同时存在点的时候说明才有可能相遇,否则起点和终点不连通
{
//从节点少的队列开始拓展时间复杂度较小
//因为节点少的队列,它拓展出来的分支也少,从而能避免枚举那些无意义的字符串
if(q1.size() < q2.size()) t = extend(q1,qa,qb,a,b);
else t = extend(q2,qb,qa,b,a);
if(t <= 10) return t;
}
return 11;//如果没有结果的话,就返回一个大于10的数,代表不成功
}
int main()
{
cin>>A>>B;
while(cin>>a[n]>>b[n]) n++;
int t = bfs(A,B);
if(t > 10) puts("NO ANSWER!");
else printf("%d",t);
return 0;
}
写的很清楚%%%
orz
代码有问题啊
建议更正QAQ
正确代码如下:
好的,才注意到数据加强了,已修改hhh
应该加上一句
if(A==B) return 0;
还有dalao的代码有一点问题吧
还有dalao的代码有一点问题吧
太棒了!!