连连看与一种巧妙的广度优先搜索

连连看 是一种益智游戏：把两张相同的图片“连接”在一起就可消除它们，全部消除后就胜利，如下图所示：

但两张相同的图片是否可以“连接”需要遵从一定的规则，如图：

A与B、C或D都可以“连接”而消除（当然只能从B、C或D中选择一个消除），但P与Q不能“连接”而消除。这里面的规则是：连接路径上的“转弯”不能超过2个，否则不可“连接”。A到B直接连接无转弯，A到C有一个转弯，A到D有两个；而P到Q至少需要3个转弯，于是不能连接而消除。

如果要制作一个连连看游戏，核心算法是要在一个M * N的矩阵上找出两个点的“最短路径”，满足：

1. 转弯数最少
2. 经过的点最少

其中第一点是最关键的：它可以判定两个点是否可以连接；第二点起辅助作用：如果我们要给玩家显示一个提示、展示一条可以连接的路径，那算法最好能指出一条在转弯数一定的情况下所经过点最少的路径。

谈到图的两点间最短路径，我们会想到用于无权图的广度优先搜索（BFS）和带权图的Dijkstra算法。那么对于连连看的M * N矩阵来说，究竟可以抽象成有权图呢还是无权图？如果有，权重又是什么呢？显然，简单地把矩阵的点对应到图的顶点、把矩阵点与点之间的直接联系（上下左右）对应成图的边是不行的——这样的路径没有考虑转弯。

考虑下图：

其中，红线经过的是从A出发可直达的点，蓝线经过的是从A出发经1个转弯可达的点，绿线经过的是从A出发经2个转弯可达的点……照此，如果把矩阵的点对应到一张图的顶点，从矩阵的一个点到从它出发不转弯可直达的每个点连一条边，则BFS可搜索从一个点出发到另一个点的“转弯最少”的路径，是不是很妙？抽象一下：对图来说，点的本质是状态，边的本质是状态之间的联系。就本文来说，点还是矩阵的点，但边已经不是矩阵点与点之间简单、直接的联系（上下左右），而是以是否可“直达”作为联系。

以上算法解决了上面第一个问题：找出转弯数最少的路径。但是如何在转弯数最少的同时找出经过的点也最少的路径呢？上面的算法并不能保证第二点。我们要对它加以修改。

我们知道BFS依靠队列（queue）来实现，我们依次处理队列中的元素。这些元素在进队时遵照着一种“层次关系”：距出发点“层次最近”的点先进队，然后下一层。一般来说，同一层的点的进队次序并不重要，因为我们一般并不区分同一层次的点：它们在BFS最短路径中地位相同。但是，对于本文来说，同一层次的点所对应的矩阵路径可能是不同长度的（虽然转弯数相同，即层次相同）。我们可以通过指定同一层次的点的进队次序来实现上面第二点要求：先进队距出发点的矩阵路径较近的点，再进队较远的点。这样，我们就用BFS实现了“二维度”最短路径搜索，是不是很妙？

JavaScript实现如下：

  //b是一个M * N的二维数组，代表矩阵。p1、p2是矩阵上的两个点
  function linkable(b, p1, p2) {
    var m = b.length;
    var n = b[0].length;
    var start = p1.x * n + p1.y; //二维坐标转换为一维以便处理
    var target = p2.x * n + p2.y;
    var total = m * n;
    var found = new Array(total);//记录已进队／处理的点
    var turn = new Array(total); //记录每个点的转弯数
    var q = [];
    q.push(start);
    found[start] = true;
    turn[start] = -1;

    //为了让p2能被搜索到，临时把它标记为空白
    var ch = b[p2.x][p2.y];
    b[p2.x][p2.y] = null;

    //上下左右四个方向
    var d = [[0, 1], [1, 0], [0, -1], [-1, 0]];

    var p;
    while (q.length > 0) {
      p = q.shift();
      if (p == target) {
        break;
      }
      else if (turn[p] == 2) { //不再处理2个以上的转弯
        continue;
      }
      else {
        var i = Math.floor(p / n);
        var j = p % n;
        var stop = new Array(4);
        for (var s = 1;; s++) {
          var k;
          //向上下左右各走s步，由近至远，保证要求2得以实现
          for (k = 0; k < 4; k++) {
            if (stop[k]) {
              continue;
            }
            var x = i + d[k][0] * s;
            var y = j + d[k][1] * s;
            var l = x * n + y;
            //注意这个条件：(!found[l] || turn[l] > turn[p])，详见附注1
            if (x >= 0 && x < m && y >= 0 && y < n && !b[x][y] && (!found[l] || turn[l] > turn[p])) {
              if (!found[l]) {
                q.push(l);
                found[l] = true;
                turn[l] = turn[p] + 1;
              }
            }
            else { //遇到障碍或走出矩阵边界则停止
              stop[k] = true;
            }
          }
          //四个方向都停止后终止
          for (k = 0; k < 4; k++) {
            if (!stop[k])
              break;
          }
          if (k == 4) {
            break;
          }
        }
      }
    }

    //恢复p2的内容
    b[p2.x][p2.y] = ch;

    return p == target;
  }

完整代码在https://github.com/coin8086/linkup。

在研读代码之前，不妨先来几局连连看吧：http://huiming.io/linkup/

附注1:

用以上BFS算法实现时，要注意以下情况：

X、Y表示不同的图形，当测试从x1是否可达x2时，0、1分别表示从x1出发经0/1个转弯可达的点，并且这些点已经进队（或者已处理），当处理点a时，如果点b已经进队，此时应当“越过”点b、把点b左边的点进队，否则得出的最短路径就经过2个转弯而不是1个。请读者仔细考虑。

附注2:

除了上述BFS，亦可把矩阵做如下变换成一个带权图，然后应用带权图的一般搜索方法来求最短路径。如下图所示：

定义图的顶点为矩阵点之间的连接。如图中点x到a、b、c、d四点的连接对应着1、2、3、4四点，其中边1-3、2-4的权为0，因为路径1-3、2-4无转弯，边1-2、2-3、3-4、4-1的权为1，因为路径上有一个转弯。要搜索x到另一点x2的最短路径，需分别从1、2、3、4四点出发寻找与x2接邻的四点，从4 * 4 = 16种选择中找一条最短的路径。 因此Dijstra可能不是最佳选择，我们需要求任意两点间的最短路径，可利用Floyd-Warshall算法。