题目描述
已知有两个字串 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。
输入
第一行为两个字符串，第二行至文件尾为变换规则
AB
A1B1
A2B2 |-> 变换规则
... ... / 所有字符串长度的上限为 20。
输出
若在 10 步（包含 10步）以内能将 A变换为变换为B ，则输出最少的变换步数；否则输出"NO ANSWER!"
样例输入
abcd xyz abc xu ud y y yz
样例输出
3
(⊙o⊙)…
大概并不是很简单，我以为BFS就行...
但是.....
时间超限...
尴尬，GG
(⊙o⊙)…双向BFS弄完了就只剩下一点string的东西了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<map> using namespace std; const int N=11; struct Node { string s; int d; }; map<string,int> m1,m2; queue<Node> q1,q2; string change[N][2],ss; Node s1,s2; int k,ans; int dbfs() { while(!q1.empty()||!q2.empty()) { if(q1.front().d+q2.front().d>10) break; s1=q1.front(); int len=s1.s.length(); for(int i=0;i<len;i++) { for(int j=0;j<k;j++) { int tmp=change[j][0].length(); ss=s1.s; if(i+tmp-1<len&&!s1.s.compare(i,tmp,change[j][0])&&!m1.count(ss.replace(i,tmp,change[j][1]))) { s2.s=ss; s2.d=q1.front().d+1; m1[s2.s]=s2.d; q1.push(s2); if(m2.count(s2.s)) { return s2.d+m2[s2.s]; } } } } q1.pop(); s1=q2.front(); len=s1.s.length(); for(int i=0;i<len;i++) { for(int j=0;j<k;j++) { int tmp=change[j][1].length(); ss=s1.s; if(i+tmp-1<len&&!s1.s.compare(i,tmp,change[j][1])&&!m2.count(ss.replace(i,tmp,change[j][0]))) { s2.s=ss; s2.d=q2.front().d+1; m2[s2.s]=s2.d; q2.push(s2); if(m1.count(s2.s)) { return s2.d+m1[s2.s]; } } } } q2.pop(); } puts("NO ANSWER!"); exit(0); return 0; } int main() { cin>>s1.s>>s2.s; if(s1.s==s2.s){cout<<0<<endl;return 0;} s1.d=s2.d=0; q1.push(s1);q2.push(s2); m1[s1.s]=0;m2[s2.s]=0; while(cin>>change[k][0]>>change[k][1])k++; cout<<dbfs()<<endl; return 0; }
RE的，谁大概给我看看为什么...
#include<cstdio> #include<iostream> #include<map> #include<string> #include<queue> using namespace std; typedef struct{string s;int d;}point; map<string,int> m1,m2; queue<point> q1,q2; string change[6][2],ss; point s1,s2; int k,ans; bool dbfs(){ while(!q1.empty()&&!q2.empty()){ if(q1.front().d+q2.front().d>10)return false; s1=q1.front(); int len=s1.s.length(); for(int i=0;i<len;i++) for(int j=0;j<k;j++){ int tmp=change[j][0].length(); ss=s1.s; if(i+tmp-1<len&&!s1.s.compare(i,tmp,change[j][0])&&!m1.count(ss.replace(i,tmp,change[j][1]))){ s2.s=ss; s2.d=q1.front().d+1; m1[s2.s]=s2.d; q1.push(s2); if(m2.count(s2.s)){ans=s2.d+m2[s2.s];return true;} } } q1.pop(); s1=q2.front(); len=s1.s.length(); for(int i=0;i<len;i++) for(int j=0;j<k;j++){ int tmp=change[j][1].length(); ss=s1.s; if(i+tmp-1<len&&!s1.s.compare(i,tmp,change[j][1])&&!m2.count(ss.replace(i,tmp,change[j][0]))){ s2.s=ss; s2.d=q2.front().d+1; m2[s2.s]=s2.d; q2.push(s2); if(m1.count(s2.s)){ans=s2.d+m1[s2.s];return true;} } } q2.pop(); } return false; } int main(){ cin>>s1.s>>s2.s; if(s1.s==s2.s){cout<<0<<endl;return 0;} s1.d=s2.d=0; q1.push(s1);q2.push(s2); m1[s1.s]=0;m2[s2.s]=0; while(cin>>change[k][0]>>change[k][1])k++; if(dbfs())cout<<ans<<endl; else printf("NO ANSWER!"); return 0; }
AC的...大概我还是不明白为什么RE...