you are given a m x n 2D grid initialized with these three possible values.
-1 is a wall, 0 is a gate. INF is empty.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
用queue儲存gates, 從gate出發, if empty, +1 distance
def wallsAndGates(self, rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
if not rooms: return
m, n = len(rooms), len(rooms[0])
q = []
for i in range(m):
for j in range(n):
if rooms[i][j] == 0:
q.append((i, j))
step = 0
while q:
step += 1
size = len(q)
while size > 0:
i, j = q.pop(0)
for dy, dx in ((0, 1), (1, 0), (0, -1), (-1, 0)):
y, x = i + dy, j+ dx
if not (0 <= y < m and 0 <= x < n): continue
if rooms[y][x] == 2147483647:
rooms[y][x] = step
q.append((y, x))
size-=1
317. Shortest Distance from All Buildings
You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:
Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.
def shortestDistance(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
record = [[0] * n for _ in range(m)] # step sum
count = [[0] * n for _ in range(m)] # reach building count
def bfs(i, j, record):
visit = [[False] * n for _ in range(m)]
q = [(i, j)]
step = -1
while q:
step += 1
for _ in range(len(q)):
x, y = q.pop(0)
if visit[x][y]: continue
visit[x][y] = True
record[x][y] += step
count[x][y] += 1
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
nx = x + dx
ny = y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0:
q.append((nx, ny))
building_cnt = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
building_cnt += 1
bfs(i, j, record)
res = float('inf')
for i in range(m):
for j in range(n): # check all buildings reached
if grid[i][j] not in (1, 2) and count[i][j] == building_cnt:
res = min(res, record[i][j])
return res if res != float('inf') else -1
909. Snakes and Ladders
牛耕式轉行法,注意行列變換
BFS
A visit set 避免loop
"""
matrix 是牛耕式轉折法,由底往上
利用num求出a,b 後,真正的idx落在 board[-a-1][b if a % 2 == 0 else -b-1]
"""
class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
count = 0
visit = set([1])
bfs = [1]
while bfs:
count += 1
size = len(bfs)
for _ in range(size):
x = bfs.pop(0)
for num in range(x + 1, x + 7):
a, b = (num - 1) // n, (num - 1) % n
nxt = board[-a-1][b if a % 2 == 0 else -b-1]
if nxt != -1:
num = nxt
# 直接走到end point
if num == n*n:
return count
if num not in visit:
visit.add(num)
bfs.append(num)
return -1