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

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

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算法。