Number of Islands, Rotting Oranges, Walls and Gates.
Многоисточниковый BFS для задач на сетках. Подсчёт островов, распространение, заполнение.
Условие:
Дана двумерная сетка grid, состоящая из символов '1' (земля) и '0' (вода). Верните количество островов.
Остров окружён водой и образован соединением соседних по горизонтали или вертикали земель.
Примеры:
Ввод: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Вывод: 1
Ввод: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Вывод: 3
Ограничения:
💡 Подсказка: Проходите по каждой клетке. При встрече '1' запускайте BFS, помечая всю компоненту связности (заменяя '1' на '0').
Решение:
from collections import deque
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def bfs(r, c):
queue = deque([(r, c)])
grid[r][c] = '0'
while queue:
row, col = queue.popleft()
for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
nr, nc = row + dr, col + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
grid[nr][nc] = '0'
queue.append((nr, nc))
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
bfs(i, j)
count += 1
return countОбъяснение:
Сложность:
Условие:
Дана сетка m x n, где каждая клетка может иметь одно из трёх значений:
0 — пустая клетка1 — свежий апельсин2 — гнилой апельсинКаждую минуту любой свежий апельсин, соседствующий (4 направления) с гнилым, становится гнилым.
Верните минимальное количество минут, которое должно пройти, чтобы все апельсины стали гнилыми. Если это невозможно, верните -1.
Примеры:
Ввод: grid = [[2,1,1],[1,1,0],[0,1,1]]
Вывод: 4
Ввод: grid = [[2,1,1],[0,1,1],[1,0,1]]
Вывод: -1
Ввод: grid = [[0,2]]
Вывод: 0
Ограничения:
💡 Подсказка: Используйте многоисточниковый BFS. Добавьте все гнилые апельсины в очередь изначально. Считайте количество свежих апельсинов.
Решение:
from collections import deque
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
# Находим все гнилые апельсины и считаем свежие
for i in range(rows):
for j in range(cols):
if grid[i][j] == 2:
queue.append((i, j))
elif grid[i][j] == 1:
fresh += 1
if fresh == 0:
return 0
minutes = 0
directions = [(1,0), (-1,0), (0,1), (0,-1)]
while queue and fresh > 0:
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
minutes += 1
return minutes if fresh == 0 else -1Объяснение:
Сложность:
Условие:
Дана сетка m x n с тремя типами клеток:
-1 — стена или препятствие0 — воротаINF (2147483647) — пустая комнатаЗаполните каждую пустую комнату расстоянием до ближайших ворот. Если комната не может достичь ворот, оставьте INF.
Примеры:
Ввод: rooms = [
[INF, -1, 0, INF],
[INF, INF, INF, -1],
[INF, -1, INF, -1],
[ 0, -1, INF, INF]
]
Вывод: [
[ 3, -1, 0, 1],
[ 2, 2, 1, -1],
[ 1, -1, 2, -1],
[ 0, -1, 3, 4]
]
Ограничения:
💡 Подсказка: Используйте многоисточниковый BFS. Добавьте все ворота в очередь изначально.
Решение:
from collections import deque
def wallsAndGates(rooms):
if not rooms:
return
rows, cols = len(rooms), len(rooms[0])
queue = deque()
# Находим все ворота
for i in range(rows):
for j in range(cols):
if rooms[i][j] == 0:
queue.append((i, j))
directions = [(1,0), (-1,0), (0,1), (0,-1)]
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == float('inf'):
rooms[nr][nc] = rooms[r][c] + 1
queue.append((nr, nc))Объяснение:
Сложность:
Условие:
Дана двумерная сетка grid, состоящая из символов '1' (земля) и '0' (вода). Верните максимальную площадь острова.
Остров окружён водой и образован соединением соседних по горизонтали или вертикали земель.
Примеры:
Ввод: grid = [
[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]
]
Вывод: 6
Ограничения:
💡 Подсказка: BFS для каждой компоненты связности. Считайте количество клеток в компоненте.
Решение (BFS версия):
from collections import deque
def maxAreaOfIsland(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
max_area = 0
def bfs(r, c):
queue = deque([(r, c)])
grid[r][c] = 0 # Помечаем как посещённый
area = 1
while queue:
row, col = queue.popleft()
for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
nr, nc = row + dr, col + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 0
area += 1
queue.append((nr, nc))
return area
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
max_area = max(max_area, bfs(i, j))
return max_areaОбъяснение:
Сложность:
| Задача | Ключевая идея |
|---|---|
| Number of Islands | BFS для каждой '1', mark as '0' |
| Rotting Oranges | Многоисточниковый BFS, счётчик fresh |
| Walls and Gates | Многоисточниковый BFS от ворот |
| Max Area of Island | BFS с подсчётом площади |
Проблема: В Rotting Oranges нужно проверять, остались ли свежие.
# ❌ Неправильно — нет проверки fresh
while queue:
...
return minutes # Может вернуть минуты, даже если остались свежие!
# ✅ Правильно
while queue and fresh > 0:
...
return minutes if fresh == 0 else -1Почему это неправильно: Если остались свежие апельсины, возвращаем -1.
Проблема: Нужно добавить все источники в очередь изначально.
# ❌ Неправильно — только один источник
queue = deque([(start_row, start_col)])
# ✅ Правильно — все источники
for i in range(rows):
for j in range(cols):
if grid[i][j] == 0: # Все ворота/гнилые
queue.append((i, j))Почему это неправильно: Многоисточниковый BFS требует все начальные точки в очереди.
BFS: Задачи на сетках — многоисточниковый BFS для распространения и подсчёта компонент.
Ключевые приёмы:
Далее: BFS: Кратчайший путь