[NOIP2002 提高组] 字串变换 题解 前言 双向广搜的代码又臭又长。 讲解 思路 看数据范围，显然普通爆搜（应该）是不能过的，那么我们在这个基础上优化。不难想到，优化可以是把普通广搜改成双向广搜，即从两头搜。 那么，什么是双向广搜？ 双向广搜，就是在已知搜的起点和搜的终点是什么，要让你求步数或其他啥的对广搜的优化。双向广搜字面意思，就是从起点和终点两头一起搜，用到两个队列。如果搜到一起了，那么就是通的，也就是最短路径（因为是广搜嘛）。如果一直到两个队列一个空了，那么有一边没路了。 就比如走迷宫，在确定终点和起点在哪里的情况下，两边正常广搜，可以共用一个标记数组，也可以用两个分开的数组。如果撞在一起了，那么这个迷宫是通的，如果你想输出步数，用数组来记录一下也可以。如果两边队列有一个空了，那说明这个迷宫走不通。 这个题也是用双向广搜，从初始字符串和终点字符串两边搜，初始字符串那边因为是顺着搜，所以就按照正常的变换方式；终点字符串那边因为是倒着搜，所以就按照变换方式相反的方式变，也可以说把 →\texttt{→}→ 符号变成 ←\texttt{←}← 符号。 代码 别抄，代码风格难看，且一堆 debug。

算法：广度优先搜索 思路：每次字符串入队列后找可以执行的操作（即看一下有没有可以修改的串），把修改之后的字符串入队列，记录修改的次数。 注意：每次找可以修改的串处理完之后要从这个位置继续往后找看这个字符串后面有没有可以修改的子串。 技巧：这个题使用STL可以大幅减少码量。

#include <iostream> #include <string> using namespace std; string a,b; string ra[7],rb[7]; struct node{ string cur;//当前字符串 int cs;//当前已修改次数 }q[2000000]; int main() { cin>>a>>b; int i=1; while(cin>>ra[i]>>rb[i]) { i++; } i-=1; }