链接:登录—专业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;
}