已知有两个字串 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 ’
共进行了 3 次变换，使得 A 变换为 B 。
输入格式：
输入格式如下：
A B
A1? B1?
A2? B2? -> 变换规则
... ... /
所有字符串长度的上限为 20 。
输出格式：
输出至屏幕。格式如下：
若在 10 步（包含 10 步）以内能将 A 变换为 B ，则输出最少的变换步数；否则输出"NO ANSWER!"
abcd xyz abc xu ud y y yz
3
思路：双向广搜
#include<cstring> #include<cstdio> #define M 100005 #define MM 55 using namespace std; int n, add[10], xl[10], yl[10]; char q[M][MM]; char p[M][MM]; char x[10][MM], y[10][MM]; int main() { int i, j, k, xx, step, len; char jiewei; scanf("%s%s", q[0], p[0]); jiewei = p[0][strlen(p[0])]; while(scanf("%s%s", x[n], y[n]) == 2) { xl[n] = strlen(x[n]), yl[n] = strlen(y[n]); add[n] = yl[n] - xl[n]; n++; } if(n == 0) { //判断两个字符串在不能变换的情况下能否相同 if(strcmp(q[0], p[0]) == 0) printf("0\n"); //strcmp函数，判断两个字符串是否相同，当s1<s2时，返回为负数；当s1==s2时，返回值= 0；当s1>s2时，返回正数 else printf("NO ANSWER!\n"); return 0; } int l1 = 0, r1 = 0, s1 = 0; int l2 = 0, r2 = 0, s2 = 0; for(step = 1; step <= 5; step++) { for(i = 0; i < n; i++) for(j = l1; j <= r1; j++) for(len = strlen(q[j]), k = 0; k < len && len+add[i] < 60; k++) if(strncmp(x[i], q[j]+k, xl[i]) == 0) { s1++; strncpy(q[s1], q[j], k); //strncpy函数，将字符串src中最多n个字符复制到字符数组dest中 strncpy(q[s1]+k, y[i], yl[i]); strncpy(q[s1]+k+yl[i], q[j]+k+xl[i], len-k-xl[i]); q[s1][len+add[i]] = jiewei; for(xx = l2; xx <= r2; xx++) if(strcmp(p[xx], q[s1]) == 0) { printf("%d\n", step+step-1); return 0; } } if(s1 != r1) l1 = r1+1, r1 = s1; for(i = 0; i < n; i++) for(j = l2; j <= r2; j++) for(len = strlen(p[j]), k = 0; k < len && len-add[i] < 60; k++) if(strncmp(y[i], p[j]+k, yl[i]) == 0) { s2++; strncpy(p[s2], p[j], k); strncpy(p[s2]+k, x[i], xl[i]); strncpy(p[s2]+k+xl[i], p[j]+k+yl[i], len-k-yl[i]); p[s2][len-add[i]] = jiewei; for(xx = l1; xx <= r1; xx++) if(strcmp(q[xx], p[s2]) == 0) { printf("%d\n", step+step); return 0; } } if(s2 != r2) l2 = r2+1, r2 = s2; } printf("NO ANSWER!\n"); return 0; }
原文：https://www.cnblogs.com/v-vip/p/9345992.html