1 问题描述及分析

连连看游戏是一种很流行的小游戏，记得在小时候去游戏厅玩街机的时候就有两台专门的连连看的机器（当然当时不叫这个名字），一个是连麻将牌、另一个是连水果图片。当时的麻将牌分好几层，相邻层的牌还可以连，看得人眼花缭乱。真是佩服能玩这游戏的人，我还是打“拳皇”比较擅长J。书中给出的Microsoft Link-up界面很漂亮，不过似乎图形只有一层，而且数量也不是很多，降低了不少难度，连我也能玩了J。

图1 广度优先路径搜索

书中给出的解法利用了广度优先搜索算法，本质上是一种建立搜索树然后剪枝的策略。具体过程如图 1所示：目标是要找到从左上角的圆形图形（设为图形1）到右下角的圆形图形（设为图形2）之间不超过3个弯的最短路径。首先在图形1所在位置向四个方向进行直线查找，如果在某一方向上找到图形2则结束。否则，记录下所有这四个方向上的空白格子，并在每一个空白格子的其他3个方向上进行直线搜索。如果仍未找到图形2则再次记录下查找过程中沿途记录下来的空白格子（要去掉已经走过的空白格子），仍然在3个方向上进行搜索。若找到则返回结果，若还未找到则说明两个图形之间不存在不超过3个弯的路径。这个算法很直观，就是在有限的转弯次数内不断构建出更大的路径网络，看看能否“覆盖”到被连接的图形，但似乎还可以进一步提高效率，下面就给出我的一些想法。

2 相同图形对之间的最短路径查找算法

以图2为例，我们的目标是找到图形1和图形2之间的最短路径，我们从图形1出发进行查找动作。由于题目要求最短路径不能超过3个弯，并且我们知道：“直线路径长度≤带有一个弯的路径长度≤带有两个弯的路径长度”，所以下面我们将分三种情况进行讨论。

为了加速程序运行，这里还引入了图3所示的两个辅助数据结构，其中每一个方块中都带有一个二进制位，用来表示在该位置上的格子是否是空格子，0代表是空格子，1代表有图形存在。虽然左右两组数据结构的内容是一样的，但是其组织方式有所不同：左边的二进制位是按列组织的，即一列的二进制位保存在一个int或者long型的变量中，多出来的位用0填满；右边的结构是按行组织的，其他与左边结构类似。这两个结构具体的功能后面用到的时候会详细介绍。

图2 改进的路径查找方法示意图

首先，应该判断是否存在图形1到图形2之间的直线路径。这一点我们可以通过他们的位置信息直接得到，例如图形1的位置是[2,2]，图形2的位置是[4,5]，很显然二者不会在一条直线上，所以直接跳过这一步。但如果二者在一条直线上的话，还需要判断他们之间是否有障碍物存在。例如，如果图形2在[5,2]的话，我们可以断定二者在同一直线上，但我们还需要检查在二者的直线路径上是否还有其他图形存在。因为两个图形同在第二列上，于是我们取图3左边结构的第二列变量C2（这里假设是一个8位的Byte变量），然后做val=C2&00110000，注意其中的两个1是用来测试在图2的第二列上是否有非空的格子。如果val=0则说明两个图形间存在直线路径，否则说明二者之间不存在直线路径。这一过程的时间复杂度为O(1)。

第二步，查找二者之间是否存在转弯一次的路径。从图中我们可以清楚地看到，这样的路径只有两条，他们组成了一个矩形，图3中蓝色的矩形就是两条路径的组合而成。我们可以用上面的方法分别来测试这两条路径上是否有障碍存在，如果没有障碍则作为最短路径返回，否则就要进行第三步。这一步的时间复杂度也是O(1)。

图3 辅助数据结构

第三步，查找两个图形间是否存在转弯三次的路径。首先我们用书中给出的方法在蓝色矩形内部进行路径查找，但是限制只在“向右”和“向下”两个方向上进行操作。如果没找到所需路径，则需要再次扩大搜索范围。如图2所示，在这一步我们需要把搜索方向在“向上”和“向左”两个方向上扩展，所获得的路径分别用红色框和粉色框表示，这个动作类似于把蓝色框向上和向左拉伸。对于获得的路径上的3条线段，我们只需用第一步所提到的方法来查找是否存在障碍即可，若3条线段都没有障碍则返回该路径作为最短路径；否则继续向两个方向扩展搜索范围直到搜索范围到达格子的边界，若仍未找到则认为两个图形间没有符合条件的最短路径。可以看出，由于不需要对同时对4个方向上所有空闲格子进行广度优先搜索操作，第三步的时间复杂度应该低于书中所给出的算法。

3 扩展问题的研究

扩展问题1说的是(1)是否可以通过维护任意两个格子之间的最短路径来实现快速搜索。(2)在每次消去两个格子之后，自然更新要更新需要维护的数据，这样的思路有哪些优缺点，如何实现。

粗略想来，由于用户每次只能消除一对图形，即只会用到一个最短路径，但由于实现并不知道用户会选择哪一对图形，所以需要事先计算出所有可能的最短路径并保存起来。此外，采用这种方法的话似乎每次用户消去一对相同图像之后都需要重新计算出当前所有可能被连接的相同图形之间最短路径，这是因为当某些图像被消去之后可能会产生很多新路径，而我们又不能确定这些空出来的格子到底能够影响哪些路径，所以就只好都重新计算一遍。其缺点很明显就是每次消去图形动作之后重新计算所有可能的最短路径所需要消耗的时间；而该方法的优点则是可以很快地判断两个相同图形之间是否存在满足条件的最短路径。

如果用户很厉害，每次都能选中可以消除的图形对，那么用这种方法浪费的时间就会相当可观，毕竟用户未选中的其他可以连接的图形对之间的最短路径都被浪费掉了；而如果用户很差劲，每轮选择的次数都远远大于当前可能的连接数量时，该方法就会比书中正文提到的方法高效。但这种情况是比较少的，因为在整个游戏中用户主要是会用眼睛“找”而不是频繁的用鼠标去“试”。所以总的来看，维护所有最短路径的方法的效率相对比较低。

参考来源：http://www.cnblogs.com/bvbook/archive/2008/07/28/1254266.html