0490：迷宫（★）

2016-05-04 约 503 字预计阅读 2 分钟次阅读

力扣第 490 题

题目

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

给你一个大小为 m x n 的迷宫 maze ，以及球的初始位置 start 和目的地 destination ，其中 start = [start_row, start_col] 且 destination = [destination_row, destination_col] 。请你判断球能否在目的地停下：如果可以，返回 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 <= start_row, destination_row <= m
0 <= start_col, destination_col <= n
球和目的地都在空地上，且初始时它们不在同一位置
迷宫 至少包括 2 块空地

分析

bfs 或 dfs 遍历即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
        m, n = len(maze), len(maze[0])
        Q, vis = deque([tuple(start)]), {tuple(start)}
        while Q:
            i, j = Q.popleft()
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                x, y = i, j
                while 0<=x+dx<m and 0<=y+dy<n and maze[x+dx][y+dy]==0:
                    x, y = x+dx, y+dy
                if (x, y) not in vis:
                    if [x, y] == destination:
                        return True
                    Q.append((x, y))
                    vis.add((x, y))
        return False

64 ms

目录

0490：迷宫（★）

题目

分析

解答