题目描述
https://www.acwing.com/problem/content/192/
输入样例
abcd xyz
abc xu
ud y
y yz
输出样例
3
C++ 代码(哈希表Hash)
#include <bits/stdc++.h>
#include <unordered_map>
#define int long long
using namespace std;
const int N=6;
int n;
string a[N],b[N];
int extend(queue<string>& q,unordered_map<string,int>& da,unordered_map<string,int>& db,string a[],string b[]){
string t=q.front();
q.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]){
string state=t.substr(0,i)+b[j]+t.substr(i+a[j].size());
if(db.count(state)) return da[t]+1+db[state];
if(da.count(state)) continue;
da[state]=da[t]+1;
q.push(state);
}
return 11;
}
int bfs(string A,string B){
queue<string> qa,qb;
unordered_map<string,int> da,db;
qa.push(A),da[A]=0;
qb.push(B),db[B]=0;
while(qa.size() && qb.size()){
int t;
if(qa.size()<=qb.size()) t=extend(qa,da,db,a,b);
else t=extend(qb,db,da,b,a);
if(t<=10) return t;
}
return 11;
}
signed main(){
string A,B;
cin>>A>>B;
while(cin>>a[n]>>b[n]) n++;
int step=bfs(A,B);
if(step>10) puts("NO ANSWER!");
else cout<<step<<endl;
return 0;
}
666