前端算法--迷宫问题

迷宫问题

我们常常会遇到各种迷宫问题，即从起点走到终点，会有哪些路径：

image.png

或者是求起点到终点最短路径：

image.png

对于这类迷宫问题，我们使用程序化的思想，可以简单的抽象成一个M*N的二维数组矩阵，如下：

1
2
3
4
5
6
7
var matrix = 
    [[0, 1, 0, 0, 0, 0]
    [0, 1, 0, 1, 0, 0]
    [0, 0, 0, 0, 0, 1]
    [1, 1, 0, 0, 0, 0]
    [1, 1, 0, 0, 0, 0]
    [1, 1, 0, 0, 0, 0]]

上面二维数组中，取左上角为起点，右下角为终点，每个点有上下左右一共4个方向可以走，0表示通路可以通过，1表示障碍物不能通过，求从起点到终点共有多少种走法。

如下所示其中一种走法，我们用“#”代表走过的路径：

image.png

我们可以很容易的找到1种走法，当然这只是对于矩阵比较小的情况下，如果矩阵足够大，那么就需要转换成程序语言来解答了。

深度优先搜索

深度优先搜索也叫深度优先遍历是一种常见的搜索方法，它的特点就是一条路走到深，不撞南墙不回头。深度优先遍历迷宫，流程如下：

  1. 访问起点s。
  2. 依次从s的未被访问的邻接点出发，在某一方向上进行搜索，直至该方向搜索完毕，并且和s有路径相通的点都被访问。
  3. 若此时还有未被访问的节点，则从一个未被访问的节点出发，重新进行深度搜索，直到所有节点均被访问为止。
  4. 循环上述操作，直到访问到终点e为止。

在进行搜索的同时，我们需要增加一些判断条件来规避一些非法的路径状态，

  1. 当前节点是通路。
  2. 当前节点没有超过迷宫范围。
  3. 当前节点在同一路径中不应被访问第二次。

最后，在搜索的同时需要记录访问过的路径，根据上面的思路，转换成JavaScript代码，我们采用递归来实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
var mazeSearch = function(){
    var matrix = 
        [[0,1,0,0,0,0],
         [0,0,0,1,0,0],
         [0,0,1,0,0,1],
         [1,1,0,0,0,0],
         [1,1,0,0,0,0],
         [1,1,0,0,0,0]]
    
    var m = matrix.length
    var n = matrix[0].length
    // 此数组用来记录当前节点是否被访问过
    var visited = new Array(m).fill('').map((d)=>new Array(n).fill(false)) 

    var dirs = [[0,1],[0,-1],[1,0],[-1,0]] // 当前节点可走的4个方向，分别对应右，左，上，下


    var dfs = function(x,y,path){
        // 到达终点
        if (x == m-1 && y == n-1) {
            console.log(path) // 打印当前路径
            return 
        }

        for (var dir of dirs) {

            var nx = x + dir[0]
            var ny = y + dir[1]
            // 分别判断当前节点是否是有效节点
            if (nx < m && // 迷宫边界
                nx >=0 && 
                ny < n && 
                ny >=0 && 
                matrix[nx][ny] == 0 && // 是否通路0：通路1：障碍
                visited[nx][ny] == false) {// 是否已访问过
                // 当访问该节点时，标记已访问
                visited[nx][ny] = true
                // 进入递归，每次递归都表示一个完整路径
                // 需要传入当前节点和已经访问过的路径
                dfs(nx,ny,path+'-'+nx+','+ny)
                // 每次路径完成时，针对该节点需要回溯原始状态
                visited[nx][ny] = false;
                
            }
        }
    }

    // 进入起点
    dfs(0,0,'0,0')
    visited[0][0] = true
}

上述代码会打印出从起点到终点的所有路径，最终右212种走法，我们可以随机画出其中几个解法的路径，如下图：

image.png

每种路径上面的数字代表当前路径的长度即所经过的节点数，可以看到不同的路径有不同的长度，那么，我们是否能在这212种走法里面找到最短的那一种呢，这就涉及到最优解，我们只需改造部分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var mazeSearch = function(){
    ...

    var res = {
        path:null,
        len:Number.MAX_SAFE_INTEGER
    }
    var dfs = function(x,y,path){
        // 到达终点
        if (x == m-1 && y == n-1) {
            // 得到当前路径长度
            var currentLen = path.split('-').length
            // 如果当前路径小于结果路径，则取结果路径
            if (res.len > currentLen) {
                res = {
                    path:path,
                    len:currentLen
                }
            }

            return 
        }
        ...

    }

    ...

    console.log(res)

}

打印出最优解，长度为12：

1
2
3
4
{
    len: 13,
    path: "0,0-1,0-1,1-1,2-0,2-0,3-0,4-1,4-2,4-3,4-3,5-4,5-5,5"
}

通过深度优先搜索得到最优解，其核心思想是得到所有解，然后从所有解里面找到最优解，那么我们能否采取一种效率更高的办法直接得到最优解呢？

广度优先搜索

广度优先搜索也叫宽度优先遍历是一种常见的搜索方法，它的特点沿一个点向四周方向向外扩展，也就是呈一种发散状向外边扩散，依次下去，直到搜索到所有的顶点。该思想就是二叉树的层序遍历的演变，一层一层的进行遍历。

广度优先搜索通常用来求最优解，即得到结果的同时，这个结果就是最短的路径，在广度遍历时，会对节点周围相关联且未遍历的点先进行遍历，然后重复此步骤直至所有节点都被遍历。由于与一个节点相关联的节点有多个且不能同时进行遍历，所以我们需要用到队列这个数据结构模拟这种“同时”的遍历，流程和思想如下：

  1. 访问起点s。
  2. 将起点作为当前节点，遍历该点的四个方向，并压入队列，并标记为已访问过的。
  3. 依次从队列中，移出队首为当前方向上的节点，记录路径。
  4. 循环上述2，3步骤操作，直到访问到终点e为止。

同样，在进行搜索的同时，我们需要增加一些判断条件来规避一些非法的路径状态，

  1. 当前节点是通路。
  2. 当前节点没有超过迷宫范围。
  3. 当前节点在同一路径中不应被访问第二次。

根据上面的思路，转换成JavaScript代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
var mazeSearch = function(){
    var matrix = 
        [[0,1,0,0,0,0],
         [0,0,0,1,0,0],
         [0,0,1,0,0,1],
         [1,1,0,0,0,0],
         [1,1,0,0,0,0],
         [1,1,0,0,0,0]]

    var m = matrix.length
    var n = matrix[0].length
    // 此数组用来记录当前节点是否被访问过
    var visited = new Array(m).fill('').map((d)=>new Array(n).fill(false))
    var arr = [] // 队列
    var dirs = [[0,1],[0,-1],[1,0],[-1,0]]// 当前节点可走的4个方向，分别对应右，左，上，下

    // 起点入队
    arr.push({
        x:0,
        y:0,
        path: '0,0'
    })
    visited[0][0] = true

    while(arr.length) {
        var current = arr.shift() // 当前方向上节点出队

        if (current.x == m-1 && current.y == n-1) {
            console.log(current.path)// 打印当前路径
            break;
        }
        for (var dir of dirs) {
            var nx = current.x + dir[0]
            var ny = current.y + dir[1]

            // 分别判断当前节点是否是有效节点
            if (nx < m && // 迷宫边界
                nx >=0 && 
                ny < n && 
                ny >=0 && 
                matrix[nx][ny] == 0 && // 是否通路0：通路1：障碍
                visited[nx][ny] == false) {// 是否已访问过

                // 根据当前路径记录走过的路径
                var _path = current.path + '-'+nx+','+ny+''
                // 节点入队
                arr.push({
                    x:nx,
                    y:ny,
                    path:_path
                })
                // 标记已访问过
                visited[nx][ny] = true
            }
        }
    }
}

至此，我们分别使用广度优先搜素和深度优先搜索完成的迷宫问题，当然，这只是最简单的迷宫问题，类似还有很多变种。

迷宫问题变种

  • 方向增加

例如：每个点有8个方向可以移动，我们可以通过修改方向数组的方式：

1
2
var dirs = [[0,1],[0,-1],[1,0],[-1,0],[1,1],[-1,-1],[1,-1],[-1,1]]
// 分别对应右，左，上，下，右上，左下，右下，左上
  • 小球滚动题目：

在迷宫中有一个球，里面有空的空间和墙壁。球可以通过滚上，下，左或右移动，但它不会停止滚动直到撞到墙上。当球停止时，它可以选择下一个方向，求小球从起点到终点的最短路径。

这个题目中的最大不同就是小球在遇到障碍物时不会停止，而是可以向四个方向移动，直到遇到墙面才会停止，所以我们针对上面的思路，梳理出两个改动点：

  1. 把是否遇到墙壁，即迷宫边界单独判断。
  2. 将if改为while即循环判断是否是有效路径。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
shortestDistance(maze,start,destination) {

  var m = maze.length
  var n = maze[0].length
  var res = Number.MAX_SAFE_INTEGER
  var visited = new Array(m).fill('').map(d=>new Array(n).fill(false))
  var dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  // 抽离出墙面迷宫边界
  var notWall = function(x,y){
      return x >= 0 && x < m && y >= 0 && y < n;
  }
  var dfs = function(x,y,step){
      

      if(x == destination[0] && y == destination[1]) {
          res = Math.min(res,step)
          return 
      }
      for(var dir of dirs) {
          var nx = x, ny = y;
          var _step = step
          // 这里改为循环判断
          while(notWall(nx + dir[0], ny + dir[1]) && maze[nx+dir[0]][ny+dir[1]] != 1) {
              nx += dir[0];
              ny += dir[1];
              _step = _step+1
          }

          if(!visited[nx][ny]) {
              visited[nx][ny] = true
              dfs(nx,ny,_step)
              visited[nx][ny] = false
              
          }
          
      }

  }

  dfs(start[0],start[1],0)

  return res == Number.MAX_SAFE_INTEGER ? -1 : res
}
  • 其他题目

例如在迷宫中增加随机传送门，LeetCode 200.岛屿数量，LeetCode 695.岛屿最大面积 等等的题目，都是属于迷宫问题的变种，其核心思想都是采用深度优先和广度优先搜索来解决。

豫ICP备19009686号
吕小鸣的前端博客正在使用PWA，是否安装到桌面？x
吕小鸣的前端博客正在使用PWA，是否安装到桌面？x