链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

已知有两个字串 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!"

示例1

输入

复制abcd xyz abc xu ud y y yz

abcd xyz
abc xu
ud y
y yz

输出

复制3

3

做法

#include<bits/stdc++.h>
using namespace std;
string s,t,a[10],b[10];
int n;
queue<string> q1,q2;
unordered_map<string,int> mp1,mp2;
int bfs(){int step=0;q1.push(s);q2.push(t);mp1[s]=0;mp2[t]=0;while(++step<=5){ while(mp1[q1.front()]==step-1){//上一层的string tmp=q1.front();q1.pop();for(int i=0;i<n;i++){int pos=0;while(pos<tmp.size()){string ss=tmp;if(ss.find(a[i],pos)==-1) break;//子串没有包含a[i]ss.replace(ss.find(a[i],pos),a[i].size(),b[i]);//注意起始点if(mp1.find(ss)!=mp1.end()) {pos++;continue;//搜过了}if(mp2.find(ss)!=mp2.end()) return step*2-1;//会合，当前这步不算q1.push(ss);mp1[ss]=step;pos++;}}}while(mp2[q2.front()]==step-1){string tmp=q2.front();q2.pop();for(int i=0;i<n;i++){int pos=0;while(pos<tmp.size()){string ss=tmp;if(ss.find(b[i],pos)==-1) break;ss.replace(ss.find(b[i],pos),b[i].size(),a[i]);if(mp2.find(ss)!=mp2.end()) {pos++;continue;//搜过了}if(mp1.find(ss)!=mp1.end()) return step*2;mp2[ss]=step;q2.push(ss);pos++;}}}}return -1;
}
int main(){cin>>s>>t;while(cin>>a[n]>>b[n]) n++;int ans=bfs();if(ans==-1) cout<<"NO ANSWER!";else cout<<ans;
}