CV1099字串变换

题目描述 Description

已知有两个字串 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$。

输入描述 Input Description

输入格式如下：

A$ B$
A1$ B1$ \
A2$ B2$ |-> 变换规则
… … /
所有字符串长度的上限为 20。

输出描述 Output Description

若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出”NO ANSWER!”

样例输入 Sample Input

abcd xyz
abc xu
ud y
y yz

样例输出 Sample Output

数据范围及提示 Data Size & Hint

hehe

题解

#include <cstdio>
#include <cstring>
#include <cstdlib>
struct {
    char str[401];
    int sep;
}q1[20000], q2[20000];
int h1, r1, h2, r2;
char s1[6][21], s2[6][21];
int l1[6], l2[6];
int n;

void newcopy2(int start, int use)
{
    int i, j;
    r2++;
    q2[r2].sep = q2[h2].sep + 1;
    for(i = 0; i < start; i++){
        q2[r2].str[i] = q2[h2].str[i];
    }
    for(j = 0; s1[use][j] != '\0'; j++, i++){
        q2[r2].str[i] = s1[use][j];
    }
    for(j = start + strlen(s2[use]); q2[h2].str[j] != '\0'; j++, i++){
        q2[r2].str[i] = q2[h2].str[j];
    }
    for(i = 0; i < r1; i++){
        if(strcmp(q1[i].str, q2[r2].str) == 0){
            printf("%d\n", q1[i].sep + q2[r2].sep);
            exit(0);
        }
    }
}

void newcopy1(int start, int use)
{
    int i, j;
    r1++;
    q1[r1].sep = q1[h1].sep + 1;
    for(i = 0; i < start; i++){
        q1[r1].str[i] = q1[h1].str[i];
    }
    for(j = 0; s2[use][j] != '\0'; j++, i++){
        q1[r1].str[i] = s2[use][j];
    }
    for(j = start + strlen(s1[use]); q1[h1].str[j] != '\0'; j++, i++){
        q1[r1].str[i] = q1[h1].str[j];
    }
    for(i = 0; i < r1; i++){
        if(strcmp(q2[i].str, q1[r1].str) == 0){
            printf("%d\n", q2[i].sep + q1[r1].sep);
            exit(0);
        }
    }
}

void deal()
{
    int i, j;
    while(h1 <= r1 && h2 <= r2){
        if(q1[h1].sep + q2[h2].sep > 10){
            printf("NO ANSWER!\n");
            exit(0);
        }
        for(i = 0; i < strlen(q1[h1].str); i++){
            for(j = 0; j < n; j++){
                if(strncmp(s1[j], &q1[h1].str[i], strlen(s1[j])) == 0){
                    newcopy1(i, j);
                }
            }
        }
        h1++;
        for(i = 0; i < strlen(q2[h2].str); i++){
            for(j = 0; j < n; j++){
                if(strncmp(s2[j], &q2[h2].str[i], strlen(s2[j])) == 0){
                    newcopy2(i, j);
                }
            }
        }
        h2++;
    }
}

int main()
{
    scanf("%s%s", q1[0].str, q2[0].str);
    while(scanf("%s%s", s1[n], s2[n]) == 2){
        n++;
    }
    deal();
    printf("NO ANSWER!\n");
    return 0;
}