2352 - 字串变换
已知有两个字串A，B及一组字串变换的规则（至多6个规则）：
<span style="line-height:1.5;">A1 -> B1</span>
<span style="line-height:1.5;">A2 -> B2</span>
<br />
例如：A＝'abcd' B＝'xyz'
变换规则为：
'abc'->'xu' 'ud'->'y' 'y'->'yz'
则此时，A可以经过一系列的变换变为B，其变换的过程为：
共进行了三次变换，使得A变换为B。
<br />
题目输入
每个测试文件只包含一组测试数据，每组输入的第一行输入两个字符串A和B。
接下来若干行输入变换规则：
A B
A1 B1
... ... /
所有字符串长度的上限为 20。
<br />
题目输出
对于每组输入数据，若在10步（包含10步）以内能将A变换为B，则输出最少的变换步数，否则输出"NO ANSWER!"。
输入/输出样例
题目输入
abcd wyz abc xu ud y y yz
题目输出
3
C++解答
#include<iostream> #include<cstdio> #include<cstring> using namespace std; struct node { char s[30]; int dep; } list1[5010],list2[5010]; char a[7][30],b[7][30]; int n; bool check(char *s1,char *s2) { if (strlen(s1)!=strlen(s2)) return false; for (int i=0;i<strlen(s1);i++) if (s1[i]!=s2[i]) return false; return true; } bool pan1(char *s,int i,int x) { for (int j=i;j<i+strlen(a[x]);j++) if (s[j]!=a[x][j-i]) return false; return true; } bool pan2(char *s,int i,int x) { for (int j=i;j<i+strlen(b[x]);j++) if (s[j]!=b[x][j-i]) return false; return true; } void bfs() { int head1,tail1,head2,tail2,i,j,k,l; head1=tail1=head2=tail2=1; while (head1<=tail1 && head2<=tail2) { if (list1[head1].dep+list2[head2].dep>10) { printf("NO ANSWER!\n"); return ; } for ( i=0;i<strlen(list1[head1].s);i++) for ( j=1;j<=n;j++) if (pan1(list1[head1].s,i,j)) { tail1++; for (k=0;k<i;k++) list1[tail1].s[k]=list1[head1].s[k]; for (l=0;l<strlen(b[j]);l++,k++) list1[tail1].s[k]=b[j][l]; for (l=i+strlen(a[j]);l<=strlen(list1[head1].s);l++,k++) list1[tail1].s[k]=list1[head1].s[l]; list1[tail1].s[k]='\0'; list1[tail1].dep=list1[head1].dep+1; for (k=1;k<=tail2;k++) if (check(list1[tail1].s,list2[k].s)) { printf("%d\n",list1[tail1].dep+list2[k].dep); return ; } } for ( i=0;i<strlen(list2[head2].s);i++) for ( j=1;j<=n;j++) if (pan2(list2[head2].s,i,j)) { tail2++; for (k=0;k<i;k++) list2[tail2].s[k]=list2[head2].s[k]; for ( l=0;l<strlen(a[j]);l++,k++) list2[tail2].s[k]=a[j][l]; for (l=i+strlen(b[j]);l<=strlen(list2[head2].s);l++,k++) list2[tail2].s[k]=list2[head2].s[l]; list2[tail2].s[k]='\0'; list2[tail2].dep=list2[head2].dep+1; for (k=1;k<=tail1;k++) if (check(list1[k].s,list2[tail2].s)) { printf("%d\n",list1[k].dep+list2[tail2].dep); return ; } } head1++; head2++; } printf("NO ANSWER!\n"); } int main() { scanf("%s%s",list1[1].s,list2[1].s); n=1; while (scanf("%s%s",a[n],b[n])!=EOF) n++; n--; list1[1].dep=list2[1].dep=0; bfs(); return 0; }