前端算法--迷宫问题

迷宫问题

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

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