Grid BFS¶
Table of Contents¶
- 1926. Nearest Exit from Entrance in Maze (Medium)
- 1091. Shortest Path in Binary Matrix (Medium)
- 1162. As Far from Land as Possible (Medium)
- 542. 01 Matrix (Medium)
- 994. Rotting Oranges (Medium)
- 1765. Map of Highest Peak (Medium)
- 934. Shortest Bridge (Medium)
- 2146. K Highest Ranked Items Within a Price Range (Medium)
- 1293. Shortest Path in a Grid with Obstacles Elimination (Hard)
- 909. Snakes and Ladders (Medium)
- 1210. Minimum Moves to Reach Target with Rotations (Hard)
- 675. Cut Off Trees for Golf Event (Hard)
- 749. Contain Virus (Hard)
- 1730. Shortest Path to Get Food (Medium) 👑
- 286. Walls and Gates (Medium) 👑
- 490. The Maze (Medium) 👑
- 505. The Maze II (Medium) 👑
- 499. The Maze III (Hard) 👑
- 317. Shortest Distance from All Buildings (Hard) 👑
- 2814. Minimum Time Takes to Reach Destination Without Drowning (Hard) 👑
1926. Nearest Exit from Entrance in Maze¶
from collections import deque
from typing import List
# BFS
def nearestExit(maze: List[List[str]], entrance: List[int]) -> int:
m, n = len(maze), len(maze[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
q = deque([(entrance[0], entrance[1], 0)])
maze[entrance[0]][entrance[1]] = "+"
while q:
r, c, steps = q.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == ".":
if nr in [0, m - 1] or nc in [0, n - 1]:
return steps + 1
q.append((nr, nc, steps + 1))
maze[nr][nc] = "+"
return -1
maze = [["+", "+", ".", "+"], [".", ".", ".", "+"], ["+", "+", "+", "."]]
entrance = [1, 2]
print(nearestExit(maze, entrance)) # 1
1091. Shortest Path in Binary Matrix¶
from collections import deque
from typing import List
# BFS
def shortestPathBinaryMatrix(grid: List[List[int]]) -> int:
n = len(grid)
if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
return -1
if n == 1:
return 1
directions = [
(0, 1),
(1, 0),
(0, -1),
(-1, 0),
(1, 1),
(-1, -1),
(1, -1),
(-1, 1),
]
q = deque([(0, 0, 1)]) # (row, column, distance)
grid[0][0] = 1
while q:
r, c, d = q.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
if nr == nc == n - 1:
return d + 1
q.append((nr, nc, d + 1))
grid[nr][nc] = 1
return -1
grid = [[0, 0, 0], [1, 1, 0], [1, 1, 0]]
print(shortestPathBinaryMatrix(grid)) # 4
1162. As Far from Land as Possible¶
from collections import deque
from typing import List
# BFS
def maxDistance(grid: List[List[int]]) -> int:
n = len(grid)
res = -1
dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
q = deque([[i, j] for i in range(n) for j in range(n) if grid[i][j] == 1])
if len(q) == (n**2):
return res
while q:
size = len(q)
for _ in range(size):
r, c = q.popleft()
for dr, dc in dirs:
nr, nc = dr + r, dc + c
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
grid[nr][nc] = 1
q.append([nr, nc])
res += 1
return res
grid = [[1, 0, 0], [0, 0, 0], [0, 0, 0]]
print(maxDistance(grid)) # 4
542. 01 Matrix¶
from collections import deque
from typing import List
# BFS
def updateMatrix(mat: List[List[int]]) -> List[List[int]]:
m, n = len(mat), len(mat[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
dist = [[float("inf")] * n for _ in range(m)]
q = deque()
for i in range(m):
for j in range(n):
if mat[i][j] == 0:
dist[i][j] = 0
q.append((i, j))
while q:
r, c = q.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] > dist[r][c] + 1:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
return dist
mat = [[0, 0, 0], [0, 1, 0], [1, 1, 1]]
print(updateMatrix(mat))
# [[0, 0, 0], [0, 1, 0], [1, 2, 1]]
994. Rotting Oranges¶
"""
- Return the minimum number of minutes that must elapse until no cell has a fresh orange.
- Hint: Multi-source BFS to count the level.
"""
from collections import deque
from typing import List
# BFS
def orangesRotting(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
fresh = 0
q = deque()
dirs = [[1, 0], [0, 1], [0, -1], [-1, 0]]
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
q.append([i, j])
elif grid[i][j] == 1:
fresh += 1
res = 0
while q and fresh > 0:
size = len(q)
for _ in range(size):
r, c = q.popleft()
for dr, dc in dirs:
nr, nc = dr + r, dc + c
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
q.append([nr, nc])
grid[nr][nc] = 2
fresh -= 1
res += 1
return res if fresh == 0 else -1
grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
assert orangesRotting(grid) == 4
1765. Map of Highest Peak¶
from collections import deque
from typing import List
class Solution:
def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
m, n = len(isWater), len(isWater[0])
dirs = [[0, 1], [1, 0], [-1, 0], [0, -1]]
q = deque()
for i in range(m):
for j in range(n):
if isWater[i][j] == 1:
q.append((i, j))
isWater[i][j] = 0 # water
else:
isWater[i][j] = -1 # unvisited land
height = 1
while q:
size = len(q)
for _ in range(size):
r, c = q.popleft()
for dr, dc in dirs:
nr, nc = dr + r, dc + c
if 0 <= nr < m and 0 <= nc < n and isWater[nr][nc] == -1:
isWater[nr][nc] = height # visited land height
q.append((nr, nc))
height += 1
return isWater
934. Shortest Bridge¶
from collections import deque
from typing import List
# BFS + DFS; Coloring
def shortestBridge(grid: List[List[int]]) -> int:
n = len(grid)
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def dfs(r, c, queue):
grid[r][c] = 2
queue.append((r, c))
for dr, dc in directions:
nr, nc = r + dr, c + dc
if nr in range(n) and nc in range(n) and grid[nr][nc] == 1:
dfs(nr, nc, queue)
q = deque()
found = False
for r in range(n):
if found:
break
for c in range(n):
if grid[r][c] == 1:
dfs(r, c, q)
found = True
break
steps = 0
while q:
m = len(q)
for _ in range(m):
r, c = q.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if nr in range(n) and nc in range(n):
if grid[nr][nc] == 1:
return steps
elif grid[nr][nc] == 0:
grid[nr][nc] = 2
q.append((nr, nc))
steps += 1
return -1
grid = [
[1, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 0, 0, 1],
[1, 1, 1, 1, 1],
]
print(shortestBridge(grid)) # 1
2146. K Highest Ranked Items Within a Price Range¶
1293. Shortest Path in a Grid with Obstacles Elimination¶
909. Snakes and Ladders¶
1210. Minimum Moves to Reach Target with Rotations¶
675. Cut Off Trees for Golf Event¶
749. Contain Virus¶
1730. Shortest Path to Get Food 👑¶
286. Walls and Gates 👑¶
from collections import deque
from typing import List
# Multi-Source BFS
def wallsAndGates(rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
m, n = len(rooms), len(rooms[0])
visited = set()
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def addRoom(r, c):
if 0 <= r < m and 0 <= c < n and (r, c) not in visited and rooms[r][c] != -1:
q.append((r, c))
visited.add((r, c))
q = deque()
for r in range(m):
for c in range(n):
if rooms[r][c] == 0:
q.append((r, c))
visited.add((r, c))
dist = 0
while q:
for _ in range(len(q)):
r, c = q.popleft()
rooms[r][c] = dist
for dr, dc in directions:
addRoom(r + dr, c + dc)
dist += 1
if __name__ == "__main__":
rooms = [
[2147483647, -1, 0, 2147483647],
[2147483647, 2147483647, 2147483647, -1],
[2147483647, -1, 2147483647, -1],
[0, -1, 2147483647, 2147483647],
]
wallsAndGates(rooms)
assert rooms == [
[3, -1, 0, 1],
[2, 2, 1, -1],
[1, -1, 2, -1],
[0, -1, 3, 4],
]
490. The Maze 👑¶
from collections import deque
from typing import List
# BFS
def hasPathBFS(maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
m, n = len(maze), len(maze[0])
dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
q = deque([start])
maze[start[0]][start[1]] = -1
while q:
r, c = q.popleft()
if [r, c] == destination:
return True
for dr, dc in dirs:
nr, nc = r, c
while 0 <= nr + dr < m and 0 <= nc + dc < n and maze[nr + dr][nc + dc] != 1:
nr += dr
nc += dc
if maze[nr][nc] != -1:
q.append([nr, nc])
maze[nr][nc] = -1
return False
maze = [
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 1, 1],
[0, 0, 0, 0, 0],
]
start = [0, 4]
destination = [4, 4]
print(hasPathBFS(maze, start, destination)) # True
505. The Maze II 👑¶
-
Tags: Array, Depth First Search, Breadth First Search, Graph, Heap Priority Queue, Matrix, Shortest Path
import heapq
from typing import List
# Dijkstra
def shortestDistance(
maze: List[List[int]], start: List[int], destination: List[int]
) -> int:
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
m, n = len(maze), len(maze[0])
dist = [[float("inf")] * n for _ in range(m)]
dist[start[0]][start[1]] = 0
heap = [(0, start[0], start[1])]
while heap:
d, r, c = heapq.heappop(heap)
if [r, c] == destination:
return d
for dr, dc in directions:
nr, nc, nd = r, c, d
while 0 <= nr + dr < m and 0 <= nc + dc < n and maze[nr + dr][nc + dc] == 0:
nr += dr
nc += dc
nd += 1
if nd < dist[nr][nc]:
dist[nr][nc] = nd
heapq.heappush(heap, (nd, nr, nc))
return -1
maze = [
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 1, 1],
[0, 0, 0, 0, 0],
]
start = [0, 4]
destination = [4, 4]
print(shortestDistance(maze, start, destination)) # 12
499. The Maze III 👑¶
-
Tags: Array, String, Depth First Search, Breadth First Search, Graph, Heap Priority Queue, Matrix, Shortest Path
import heapq
from typing import List
# Dijkstra
def findShortestWay(maze: List[List[int]], ball: List[int], hole: List[int]) -> str:
directions = [(-1, 0, "u"), (1, 0, "d"), (0, -1, "l"), (0, 1, "r")]
m, n = len(maze), len(maze[0])
dist = [[float("inf")] * n for _ in range(m)]
dist[ball[0]][ball[1]] = 0
paths = [[""] * n for _ in range(m)]
paths[ball[0]][ball[1]] = ""
heap = [(0, "", ball[0], ball[1])]
while heap:
d, path, x, y = heapq.heappop(heap)
if [x, y] == hole:
return path
for dx, dy, direction in directions:
nx, ny, nd = x, y, d
while 0 <= nx + dx < m and 0 <= ny + dy < n and maze[nx + dx][ny + dy] == 0:
nx += dx
ny += dy
nd += 1
if [nx, ny] == hole:
break
new_path = path + direction
if nd < dist[nx][ny] or (nd == dist[nx][ny] and new_path < paths[nx][ny]):
dist[nx][ny] = nd
paths[nx][ny] = new_path
heapq.heappush(heap, (nd, new_path, nx, ny))
return "impossible"
maze = [
[0, 0, 0, 0, 0],
[1, 1, 0, 0, 1],
[0, 0, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 1, 0, 0, 0],
]
ball = [4, 3]
hole = [0, 1]
print(findShortestWay(maze, ball, hole)) # "lul"