已知有两个字串 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 xyz
abc xu
ud y
y yz

3

hehe

#include<stdio.h>

#include<string.h>

struct node

{

    char s[];

    int dep;  //变换次数

} list1[], list2[];

char a[][], b[][];

int n;

void BFS()

{

    int head1, tail1, head2, tail2, k;

    head1 = tail1 = head2 = tail2 = ;

    while(head1 <= tail1 && head2 <= tail2)

    {

        if(list1[head1].dep + list2[head2].dep > )

        {

            printf("NO ANSWER!\n");

            return ;

        }

        for(int i = ;i < strlen(list1[head1].s); i++)

            for(int j = ; j <= n; j++)

                if(strncmp(list1[head1].s + i, a[j], strlen(a[j])) == ) //寻找当前可变换的规则

                {

                  tail1++; //移动尾指针，存储变换后的字符串，以下三个for循环为变换过程

                  for(k = ; k < i; k++)

                      list1[tail1].s[k] = list1[head1].s[k];

                  for(int l = ; 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+;

                  for (k = ; k <= tail1; k++)

                    if (strcmp(list1[tail1].s, list2[k].s) == )//判断当前状态是否与逆向搜索交汇

                    {

                       printf("%d\n", list1[tail1].dep + list2[k].dep);

                       return ;

                     }

                }

        for (int i = ; i < strlen(list2[head2].s); i++) //逆向搜索同上

            for (int j = ; j <= n; j++)

                if(strncmp(list2[head2].s + i, b[j], strlen(b[j])) == )

                {

                  tail2++;

                  for(k = ; k < i; k++)

                      list2[tail2].s[k] = list2[head2].s[k];

                  for(int l = ; 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 + ;

                  for (k = ;k <= tail1; k++)

                    if (strcmp(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[].s, list2[].s);

    n = ;

    while (scanf("%s%s",a[n],b[n]) != EOF)

        n++;

n--;

    list1[].dep = list2[].dep = ;

    BFS();

    return ;

}