1099 字串变换

2002年NOIP全国联赛提高组

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 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

分类标签 Tags 点此展开

广度优先搜索搜索大陆地区 NOIP全国联赛提高组 2002年

题解：

最少步数问题妥妥的bfs
很显然队列里存的是串（可能存个数也可以就像8数码那样）
然后每次队首元素弄出来能换的都换一遍
最后每次换完的新串入队前先判断到头了没
最后说一句 String大法好0.0

ps:最后一个点数据较大，不建议开循环队列。

AC代码:

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
const int N=2e6+10;
const int M=11;
int step[N];
string a,b,s1[M],s2[M],q[N]; 
int main(){
    int n=1;
    cin>>a>>b;
    while(cin>>s1[n]>>s2[n]) n++;
    n--;//处理变换规则 
    int h=0,t=1;
    q[1]=a;
    while(h<t){
        if(step[++h]>10) break;
        for(int i=1;i<=n;i++){//每一种规则都尝试 反正数据小
            for(int j=0;j<q[h].length();j++){//可能有好几个地方可以换 所以枚举一下 
                if(!q[h].compare(j,s1[i].length(),s1[i])){//如果包含给出的串
                    q[++t]=q[h];
                    step[t]=step[h]+1;
                    q[t].replace(j,s1[i].length(),s2[i]);//将找到的字串入队 然后换掉
                    if(q[t]==b){
                        cout<<step[t];
                        return 0;
                    }
                }
            }
        }
    }
    cout<<"NO ANSWER!";
    return 0;
}

最后一个测试点：

输入数据 (只显示前20行，完整数据请点击上面按钮下载)
abaaaba abcdaba 
a b 
b d 
d e 
e f 
f g 
g c
正确答案
 8