Leetcode.Plus.490. 迷宫

由空地（用 0 表示）和墙（用 1 表示）组成的迷宫 maze 中有一个球。球可以途经空地向 上、下、左、右 四个方向滚动，且在遇到墙壁前不会停止滚动。当球停下时，可以选择向下一个方向滚动。

给你一个大小为 m x n 的迷宫 maze ，以及球的初始位置 start 和目的地 destination ，其中 start = [startrow, startcol] 且 destination = [destinationrow, destinationcol] 。请你判断球能否在目的地停下：如果可以，返回 true ；否则，返回 false 。

你可以 假定迷宫的边缘都是墙壁（参考示例）。

示例 1：

输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
输出：true
解释：一种可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。

示例 2：

输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
输出：false
解释：不存在能够使球停在目的地的路径。注意，球可以经过目的地，但无法在那里停驻。

示例 3：

输入：maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
输出：false

提示：

  • m == maze.length
  • n == maze[i].length
  • 1 <= m, n <= 100
  • maze[i][j] is 0 or 1.
  • start.length == 2
  • destination.length == 2
  • 0 <= startrow, destinationrow <= m
  • 0 <= startcol, destinationcol <= n
  • 球和目的地都在空地上，且初始时它们不在同一位置
  • 迷宫 至少包括 2 块空地
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
func hasPath(maze [][]int, start []int, destination []int) bool {
	m, n := len(maze), len(maze[0])
	visit := make([][]bool, m)
	for i, _ := range visit {
	visit[i] = make([]bool, n)
	}
	  
	var dfs func(i,j int)  
	  
	dfs = func(i, j int) {
		// 已访问不走了
		if visit[i][j] {
			return
		}
		// 标记
		visit[i][j] = true
		if i == destination[0] && j == destination[1] {
			// 到达
			return
		}
		  
		up := i-1
		down := i+1
		left := j-1
		right := j+1
		
		// 分别从四个方向走到底
		for right < n && maze[i][right] == 0 {
			right ++
		}
		// 走到底之后在前一个节点重新出发
		dfs(i, right-1)
		  
		for left>=0 && maze[i][left] == 0 {
			left --
		}
		dfs(i, left+1)
		  
		for up >= 0 && maze[up][j] == 0 {
			up --
		}
		dfs(up+1, j)
		  
		for down < m && maze[down][j] == 0 {
			down ++
		}
		dfs(down-1, j)
	}
  
	dfs(start[0], start[1])
	// 仅标记，dfs 为添加返回值，按照逻辑验证终点是否可达即可
	if visit[destination[0]][destination[1]] == true {
		return true
	}
	return false
}