codevs1099

#include<stdio.h>
#include<string.h>
struct node
{
    char s[30];
    int dep;  //为了计算转换次数
} list1[5010], list2[5010];  //记忆两个字符串的
char a[7][30],b[7][30];//记忆转换规则的
int n;

void BFS()

{
    int head1,tail1,head2,tail2,k;
    head1 = tail1 = head2 = tail2 = 1;     //head记录队列中搜索的位置  tail为向队列中插
    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(strncmp(list1[head1].s + i,a[j],strlen(a[j])) == 0)
                {
                    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(strcmp(list1[k].s,list2[k].s) == 0)
                        {
                            printf("%d\n",list1[k].dep + list2[k].dep);
                            return ;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < strlen(list2[head2].s); i++) //逆向搜索同上
            for (int j = 1; j <= n; j++)
                if(strncmp(list2[head2].s + i, b[j], strlen(b[j])) == 0)
                {
                    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 (strcmp(list1[k].s, list2[tail2].s) == 0)
                        {
                            printf("%d\n",list1[k].dep + list2[tail2].dep);
                            return ;
                        }
                }
        head1++;
        head2++;
    }
    printf("NO ANSWER!\n"); //这个地方千万别忘写了 不然就80分了
}

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;
    //printf("11111");
}