题目描述

已知有两个字串 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
\
|-> 变换规则
... ... /
所有字符串长度的上限为 20。

输出描述:

输出格式如下：
若在10步（包含 10步）以内能将A变换为B，则输出最少的变换步数；否则输出"NO ANSWER!"

示例1

输入
abcd xyz
abc xu
ud y
y yz
输出
3

解答

1.读完题目，样例模拟成功，但感觉该题挺难的，无从下手。
2.搜索网络后，才明白，因为有多种变换规则，故一次变换有多种可能，故采用广度优先遍历方法。
3.数据输入量：至多6个规则 所有字符串长度的上限为 20
4.感觉该题比较简单，编码，提交60分，测试点4,5 均RE。
5.将队列q[1000]改成q[10000]，测试点4通过，测试点5还是RE，再改大数组还是无功而返。单向搜索，80分到头。
6.采用双向搜索，参考他人代码，收获很大，但提交还是80分，无奈只好对拍，才发现字符串变换出了问题，必须整个字符串搜索完毕，按规则逐个变换才能算一步变换结束，之前的问题是，字符串只变化第一次找到的字符，没有第二次第三次查找，算法存在较大问题。
7.问题找到后，开始修改，工程量不小。
8.核心代码：p=strstr(b+d+strlen(left[i]),left[i]);//查找剩下的字符串，该题最难之处 
9.修改，提交AC。

 
#include <stdio.h>
#include <string.h>
char input[100],output[100];
int lena=0;
struct node{
    char in[30];//in[100]
    int s;//步数 
}q1[1000],q2[1000];//q[1000]
char left[10][30],right[10][30];//变换规则 
void bfs(char *input,char *output){
    int h1,t1,i,j,d,h2,t2;
    char b[30],*p;//b[100]
    
    h1=t1=0;
    strcpy(q1[t1].in,input);
    q1[t1].s=0;
    t1++;
    
    h2=t2=0;
    strcpy(q2[t2].in,output);
    q2[t2].s=0;
    t2++; 
    
    if(strcmp(q1[t1-1].in,q2[t2-1].in)==0){
        printf("%d\n",q1[t1-1].s+q2[t2-1].s);
        return;
    }
    while(h1<t1&&h2<t2){
        if(q1[h1].s+q2[h2].s>10)
            break;
        strcpy(b,q1[h1].in);
        for(i=0;i<lena;i++){//变换处理
            p=strstr(b,left[i]);
            while(p!=NULL){
                d=p-b;
                strncpy(q1[t1].in,b,d);
                strcat(q1[t1].in,right[i]);
                strcat(q1[t1].in,&b[d+strlen(left[i])]);
                q1[t1].s=q1[h1].s+1;
                for(j=0;j<t2;j++)
                    if(strcmp(q1[t1].in,q2[j].in)==0){
                        printf("%d\n",q1[t1].s+q2[j].s);
                        return;
                    }
                t1++;
                p=strstr(b+d+strlen(left[i]),left[i]);//查找剩下的字符串，该题最难之处 
            } 
        }
        h1++;
        
        strcpy(b,q2[h2].in);
        for(i=0;i<lena;i++){//变换处理
            p=strstr(b,right[i]);
            while(p!=NULL){//原来是if，现改成while 
                d=p-b;
                strncpy(q2[t2].in,b,d);
                strcat(q2[t2].in,left[i]);
                strcat(q2[t2].in,&b[d+strlen(right[i])]);
                q2[t2].s=q2[h2].s+1;
                for(j=0;j<t1;j++)
                    if(strcmp(q2[t2].in,q1[j].in)==0){
                        printf("%d\n",q1[j].s+q2[t2].s);
                        return;
                    }
                t2++;
                p=strstr(b+d+strlen(right[i]),right[i]);//用了比较长的时间才理解。 
            } 
        }
        h2++;
    }
    printf("NO ANSWER!\n");
}
int main(){
    int i,j;
    char a[30],b[30];
    scanf("%s%s",input,output);//读取变换前后字符串 
    while(scanf("%s%s",a,b)==2){//读取变换规则 
        strcpy(left[lena],a);
        strcpy(right[lena],b);
        lena++;
    }
    bfs(input,output);
    return 0;
}


来源：mrcrack