LC 0542 [M] 01 Matrix - ALawliet/algorithms GitHub Wiki
https://leetcode.com/problems/01-matrix/discuss/363902/BFS-python-explained-and-commneted-(two-approaches)
DIRS = [-1,0], [1,0], [0,-1], [0,1](/ALawliet/algorithms/wiki/-1,0],-[1,0],-[0,-1],-[0,1)
class Solution:
def updateMatrix(self, matrix):
# So this problem asks us to find the minimum distance of 0 from every cell with value 1,
# BFS should ring in your mind and instead of our single-source BFS and multiple invocations, we
# Apply multiple source BFS with a single invocation.
ROWS, COLS = len(matrix), len(matrix[0])
Q = deque()
res = [[-1 for _ in range(COLS)] for _ in range(ROWS)]
for r in range(ROWS):
for c in range(COLS):
if matrix[r][c] == 0:
# The distance to itself is 0 and add all sources here to queue
res[r][c] = 0
Q.append((r, c))
while Q:
r, c = Q.popleft()
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
# Validate all the neighbors and validate the distance as well
if 0 <= nr < ROWS and 0 <= nc < COLS and res[nr][nc] == -1:
res[nr][nc] = res[r][c] + 1
Q.append((nr, nc))
return res