每周一算法：双向广搜

题目链接

���符串变换

题目描述

已知有两个字串 A , B A,B A,B，及一组字串变换的规则（至多 6 6 6个规则）:

A 1 → B 1 A_1→B_1 A1​→B1​

A 2 → B 2 A_2→B_2 A2​→B2​

…

规则的含义为：在 A A A中的子串 A 1 A_1 A1​ 可以变换为 B 1 B_1 B1​、 A 2 A_2 A2​可以变换为 B 2 B_2 B2​…。

例如： A = A= A=abcd， B = B= B=xyz

变换规则为：

abc → xu，ud → y，y → yz

则此时， A A A可以经过一系列的变换变为 B B B

，其变换的过程为：

abcd → xud → xy → xyz

共进行了三次变换，使得 A A A变换为 B B B。

注意，一次变换只能变换一个子串，例如 A ＝ A＝ A＝=aa， B = B= B=bb

变换规则为：

a → b

此时，不能将两个 a 在一步中全部转换为 b，而应当分两步完成。

输入格式

A    B A~~B A  B

A 1   B 1 A_1~B_1 A1​ B1​

A 2   B 2 A_2~B_2 A2​ B2​

… …

第一行是两个给定的字符串 A A A和 B B B。

接下来若干行，每行描述一组字串变换的规则。

所有字符串长度的上限为 20 20 20。

输出格式

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

输入样例

abcd xyzabc xuud yy yz

输出样例

3

算法思想

根据题目描述，通过输入的规则将字串 A A A变换为 B B B，求最小步数，显然可以通过BFS求解。

分析数据范围，至多 6 6 6个规则，在 10 10 10 步（包含 10 10 10步）以内进行转换，如果直接进行BFS，在最坏情况下搜索的状态空间是 6 10 6^{10} 610，会超时，可以使用双向广搜进行处理。

双向广搜，是指从起点和终点同时开始进行BFS，双向奔赴直到找到共同的目标为止。

使用双向广搜可以把搜索空间降到 2 × 6 5 2\times 6^5 2×65，大大减少了要搜索的状态，剪枝效果明显。

使用双向广搜时要注意：

• 在双向广搜时，优先选择队列中状态数量较少的方向来扩展，可以优化搜索效率
• 在扩展时，需要将一层的所有节点扩展完，不能只扩展一个点。如下图所示，第 2 2 2层有 1 , 2 , 3 , 4 1,2,3,4 1,2,3,4四个节点，则需要把这 4 4 4个节点从队列中全部取出进行扩展。否则，找到的可能不是最少的转换次数。

  代码实现

  #include #include #include #include using namespace std;const int N = 6;int n;string A, B; //起点和终点string a[N], b[N]; //变换规则//从队列q中，将同层的节点全部扩展int extend(queue& q, unordered_map& da, unordered_map& db,     string a[N], string b[N]){    int d = da[q.front()]; //层数    while(q.size() && da[q.front()] == d) //将同层的节点全部扩展    {        string t = q.front(); q.pop();        for(int i = 0; i  A >> B;    while(cin >> a[n] >> b[n]) n ++;    int t = bfs();    if(t == -1) puts("NO ANSWER!");    else cout