Documenting LeetCode solving.
Q114
Medium. Graph
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
# BFS
q = deque()
time, fresh = 0, 0
ROWS, COLS = len(grid), len(grid[0])
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 1:
fresh += 1
if grid[r][c] == 2:
q.append([r, c])
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
while q and fresh > 0:
for i in range(len(q)):
r, c = q.popleft()
for dr, dc in directions:
row, col = dr + r, dc + c
if (row < 0 or row == ROWS or col < 0 or col == COLS or
grid[row][col] != 1):
continue
grid[row][col] = 2
q.append([row, col])
fresh -= 1
time += 1
return time if fresh == 0 else -1
Q115
663. Walls and Gates
Medium. Graph
Multi source BFS.
class Solution:
"""
@param rooms: m x n 2D grid
@return: nothing
"""
def walls_and_gates(self, rooms: List[List[int]]):
ROWS, COLS = len(rooms), len(rooms[0])
visit = set()
q = deque()
for r in range(ROWS):
for c in range(COLS):
if rooms[r][c] == 0:
q.append([r, c])
visit.add((r, c))
def addRoom(r, c):
if (r < 0 or r == ROWS or c < 0 or c == COLS or
(r, c) in visit or rooms[r][c] == -1):
return
q.append([r, c])
visit.add((r, c))
dist = 0
while q:
for i in range(len(q)):
r, c = q.popleft()
rooms[r][c] = dist
addRoom(r + 1, c)
addRoom(r - 1, c)
addRoom(r, c + 1)
addRoom(r, c - 1)
dist += 1
Β