-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0542 [M] 01 Matrix
Code with Senpai edited this page Jun 3, 2022
·
6 revisions
DIRS = [[-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
footer