[问题描述]:
已知有两个字串 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!"
[输入样例]
abcd wyz
abc xu
ud y
y yz
[输出样例]
3
分析：
双向BFS：
所谓双向搜索指的是搜索沿两个方向同时进行：
1.正向搜索：从初始结点向目标结点方向搜索。
2.逆向搜索：从目标结点向初始结点方向搜索。
当两个方向的搜索生成同一子结点时终止此搜索过程。
双向搜索通常有两种方法：
1. 两个方向交替扩展。
2. 选择结点个数较少的那个方向先扩展。
方法2克服了两方向结点的生成速度不平衡的状态,明显提高了效率。
【参考程序】：
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
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,k;
head1=tail1=head2=tail2=1;
while (head1<=tail1 && head2<=tail2)
{
if (list1[head1].dep+list2[head2].dep>10)
{
printf("NO ANSWER!\n");
return ;
}
for (int i=0;i<strlen(list1[head1].s);i++)
for (int 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 (int l=0;l<strlen(b[j]);l++,k++) list1[tail1].s[k]=b[j][l];
for (int 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<=tail1;k++)
if (check(list1[tail1].s,list2[k].s))
{
printf("%d\n",list1[tail1].dep+list2[k].dep);
return ;
}
}
for (int i=0;i<strlen(list2[head2].s);i++)
for (int 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 (int l=0;l<strlen(a[j]);l++,k++) list2[tail2].s[k]=a[j][l];
for (int 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()
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
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;
}