LC 0286 [M] Walls and Gates
Code with Senpai edited this page Oct 12, 2022
·
13 revisions
start from gates 0, use traversal to fill nearby rooms with distances if not OOB and condition passes (all pretty much the same thing):
-
rooms[nr][nc] > rooms[r][c]
# greater than 0 (gate) or -1 (wall) -
rooms[nr][nc] == 2147483647
# is empty INF -
not rooms[nr][nc] == -1 and rooms[nr][nc] == 2147483647
# is not -1 (wall) and is empty
we want to fill the EMPTY rooms, so start BFS from each GATEs
GATE = 0
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
EMPTY = 2147483647
class Solution(object):
def wallsAndGates(self, rooms: List[List[int]]) -> None:
ROWS, COLS = len(rooms), len(rooms[0])
Q = deque()
for r in range(ROWS):
for c in range(COLS):
if rooms[r][c] == GATE:
Q.append((r, c))
while Q:
r, c = Q.popleft()
for dr, dc in DIRS:
nr = r + dr
nc = c + dc
if 0 <= nr < ROWS and 0 <= nc < COLS and rooms[nr][nc] == EMPTY:
rooms[nr][nc] = rooms[r][c] + 1
Q.append((nr, nc))
footer