题目描述

本题的背景是连连看小游戏. $6 \times 6$ 的网格中分布着若干对字母 (可能重复), 玩家需要用线条连接每对相同的字母 (题目中没说线条之间能否相互交叉, 但我觉得应该不能), 线条可以超出 $6 \times 6$ 的网格区域. 下面是一个示例.

   │ C │ D │_A_│   │   │
───┼───┼───┼───┼───┼───┼
   │ B │   │   │ E │   │
───┼───┼───┼───┼───┼───┼
   │   │   │ C │ B │   │
───┼───┼───┼───┼───┼───┼
   │ C │ B │ E │   │   │
───┼───┼───┼───┼───┼───┼
   │ B │   │ D │   │   │
───┼───┼───┼───┼───┼───┼
_A_│   │   │   │   │ C │
───┼───┼───┼───┼───┼───┼

问题:

对任意一对字母, 找出它们之间的最短路径.
对任意一对字母, 找出它们之间转弯次数最少的路径.
(选做) 用最少的转弯次数连接配对所有的字母对.

以上图中的一对字母 A (那个不是颜文字) 为例, 它们之间的最短路径为:

   │ C │ D │_A_│   │   │
───┼───┼───┼───┼───┼───┼
   │ B │ * │ * │ E │   │
───┼───┼───┼───┼───┼───┼
 * │ * │ * │ C │ B │   │
───┼───┼───┼───┼───┼───┼
 * │ C │ B │ E │   │   │
───┼───┼───┼───┼───┼───┼
 * │ B │   │ D │   │   │
───┼───┼───┼───┼───┼───┼
_A_│   │   │   │   │ C │
───┼───┼───┼───┼───┼───┼

它们之间的转弯次数最少的路径为:

 * │ * │ * │ * │   │   │
───┼───┼───┼───┼───┼───┼
 * │ C │ D │_A_│   │   │
───┼───┼───┼───┼───┼───┼
 * │ B │   │   │ E │   │
───┼───┼───┼───┼───┼───┼
 * │   │   │ C │ B │   │
───┼───┼───┼───┼───┼───┼
 * │ C │ B │ E │   │   │
───┼───┼───┼───┼───┼───┼
 * │ B │   │ D │   │   │
───┼───┼───┼───┼───┼───┼
_A_│   │   │   │   │ C │
───┼───┼───┼───┼───┼───┼

注意此处路径超出了网格区域, 这是允许的.

解题思路

第 1 问显然可以直接用广度优先搜索解决. (这节课为止还没有讲到 A* 之类的算法, 就不考虑了.) 第 2 问乍一看不太明晰, 但其实也可以用广度优先搜索. 第 3 问我还没想明白.

第 1 问

搞清楚下面几个要素就能够应用广度优先搜索了.

状态(顶点): 当前格的坐标 $(x, y)$.
初始状态: 起始格的坐标, 在上面的例子中为 $(3, 0)$ (以 $6 \times 6$ 网格的左上角为 $(0, 0)$).
行动(边): 从 $(x, y)$ 格出发可以移动到 $(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)$ 中没有字母的格子.
终止状态: 终点格的坐标.

第 2 问

在第 1 问中, 我们把「一步」（一个行动或一条边）老老实实地定义成从某格上下左右移动一格. 这样就能确保在进行广度优先搜索的时候, 搜索出的路径长度是最短的. 现在, 既然我们要使转弯的次数最少, 那么「一步」就应该定义成一次转弯.

状态(顶点): $((x, y), d)$. 其中 $(x, y)$ 是当前格的坐标; $d$ 是上一次移动的方向, 取值为 $(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)$ 其中之一, 前四个各代表左, 右, 上, 下, 最后一个只在初始状态下出现, 原因稍后解释.
初始状态: $((x_0, y_0), (0, 0))$, 其中 $(x_0, y_0)$ 是起始格的坐标.
行动(边): 从状态 $((x, y), d)$ 出发, 可以到达状态 $((x, y) + n \cdot d^\prime, d^\prime)$. 其中 $n$ 为任意正整数, 代表了移动的距离; $d^\prime$ 为上下左右四个方向中任意与 $d$ 不同的方向. 两者满足: 格子 $(x, y) + n \cdot d^\prime$ 与 $(x, y)$ 之间的空间没有字母的阻隔.

提示

限制 $d^\prime$ 与 $d$ 不同是为了让每一次行动都是转向 (即不能选择和上一次行动一样的方向). 因为从初始状态出发可以选择上下左右任意一个方向, 所以将初始状态的 $d$ 特别设为 $(0, 0)$ 以与上下左右四个方向都不同 (你也可以设成 $(114, 514)$ 等任意富有个性的值).

终止状态: 终止状态的坐标就是终点格的坐标, 方向任取, 只要搜索到终点格即停止搜索即可.

简单来说, 就是将路径中的每一条线段看成一次行动即可. 另外还需注意, 每次行动中, 需要将线段上的所有格子都加入闭节点表. 这样一来即可应用广度优先搜索. 代码就不粘在这儿了, 写得有点乱.

第 3 问

你行你上, 我是真不会.