1091. Shortest Path in Binary Matrix
https://leetcode.com/problems/shortest-path-in-binary-matrix/
solution
class Solution:
def __init__(self):
self.dirs = [[0, 1], [1, 0], [0, -1], [-1, 0], [1, 1], [-1, -1], [1, -1], [-1, 1]]
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
if grid[0][0] != 0 or grid[-1][-1] != 0:
return -1
m = len(grid)
n = len(grid[0])
start = (0, 0)
target = (m - 1, n -1)
queue = collections.deque([start])
# 别忘了标记visited, 否则超时
# 注意二维bfs中,list是unhashable的, 因此用dict类似hash set. 或者和岛屿问题一样通过改变数字实现
visited = {start} # 或 visited = set((0, 0)), 即使是set中也要用tuple, list is unhashable
res = 0
while queue:
res += 1
for _ in range(len(queue)):
x, y = queue.popleft()
if (x, y) == target:
return res
for dx, dy in self.dirs:
new_x = x + dx
new_y = y + dy
if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] == 0 and (new_x, new_y) not in visited:
queue.append([new_x, new_y])
visited.add((new_x, new_y))
return -1
时间复杂度:O(mn) 空间复杂度:O(mn)
follow up
输出路径 (全部或其中一个)
# 用hashmap存上一步的坐标
Last updated