题目描述 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
3
数据范围及提示 Data Size & Hint
hehe
这个题主要是介绍了一种BFS的方法,那就是,如果根据题意,知道开始状态与最终状态的话,那么就可以考虑使用双向BFS加快效率节省时间,比方说这个题,需要用两个队列存储状态信息,然后分别交叉进行BFS,如果出现状态相同的情况,那么就输出.
需要注意几点,存储字串的字符串数组应至少40,因为变换过后,可能会出现长度为39的字符串.如果步数已经大于10步的话,立即输出NA即可
代码如下:
/*************************************************************************
> File Name: 字串变换.cpp
> Author: zhanghaoran
> Mail: chilumanxi@gmail.com
> Created Time: 2015年07月22日 星期三 08时41分10秒
************************************************************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
using namespace std;
char s1[6][21];
char s2[6][21];
struct node{
char s[40];
int step;
}q1[10000], q2[10000];
int head1 = 0, tail1 = 1;
int head2= 0, tail2 = 1;
int n;
void bfs1(int begin, int cur){
int i , j;
q1[tail1].step = q1[head1].step + 1;
for(i = 0; i < begin; i ++){
q1[tail1].s[i] = q1[head1].s[i];
}
for(j = 0; s2[cur][j] != ' '; i ++, j ++){
q1[tail1].s[i] = s2[cur][j];
}
for(j = begin + strlen(s1[cur]); q1[head1].s[j] != ' '; j ++, i ++){
q1[tail1].s[i] = q1[head1].s[j];
}
q1[tail1].s[i] = ' ';
for(i = 0; i <= tail1; i++){
if(strcmp(q2[i].s, q1[tail1].s) == 0){
printf("%d
", q2[i].step + q1[tail1].step);
exit(0);
}
}
tail1 ++;
}
void bfs2(int begin, int cur){
int i, j;
q2[tail2].step = q2[head2].step + 1;
for(i = 0; i < begin; i ++){
q2[tail2].s[i] = q2[head2].s[i];
}
for(j = 0; s1[cur][j] != ' '; j ++, i ++){
q2[tail2].s[i] = s1[cur][j];
}
for(j = begin + strlen(s2[cur]); q2[head2].s[j] != ' '; j ++, i ++){
q2[tail2].s[i] = q2[head2].s[j];
}
q2[tail2].s[i] = ' ';
for(i = 0; i <= tail2; i ++){
if(strcmp(q2[tail2].s, q1[i].s) == 0){
printf("%d
", q1[i]. step + q2[tail2].step);
exit(0);
}
}
tail2 ++;
}
int main(void){
scanf("%s%s", q1[0].s, q2[0].s);
while(scanf("%s%s", s1[n], s2[n]) == 2)
n ++;
while(head1 < tail1 && head2 < tail2){
if(q1[head1].step + q2[head2].step > 10){
printf("NO ANSWER!
");
return 0;
}
for(int i = 0; i < strlen(q1[head1].s); i ++){
for(int j = 0; j < n; j ++){
if(strncmp(s1[j], &q1[head1].s[i], strlen(s1[j])) == 0){
bfs1(i, j);
}
}
}
head1 ++;
for(int i = 0; i < strlen(q2[head2].s); i ++){
for(int j = 0; j < n; j ++){
if(strncmp(s2[j], &q2[head2].s[i], strlen(s2[j])) == 0){
bfs2(i, j);
}
}
}
head2 ++;
}
printf("NO ANSWER!
");
exit(0);
}