Number of Islands, Max Area, Word Search.
Обход сеток с помощью DFS. Подсчёт островов, площадь, поиск слов.
Условие:
Дана двумерная сетка 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
Решение:
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if (r < 0 or c < 0 or r >= rows or c >= cols or
grid[r][c] == '0'):
return
grid[r][c] = '0' # Помечаем как посещённый
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return countОбъяснение:
Сложность: O(m × n)
Условие: Найдите максимальную площадь острова (количество единиц в компоненте связности).
Решение:
def maxAreaOfIsland(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
max_area = 0
def dfs(r, c):
if (r < 0 or c < 0 or r >= rows or c >= cols or
grid[r][c] == 0):
return 0
grid[r][c] = 0
area = 1
area += dfs(r + 1, c)
area += dfs(r - 1, c)
area += dfs(r, c + 1)
area += dfs(r, c - 1)
return area
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
max_area = max(max_area, dfs(i, j))
return max_areaОбъяснение:
Сложность: O(m × n)
Условие:
Дана сетка board и слово word. Верните true, если слово существует в сетке.
Примеры:
Ввод: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Вывод: true
Решение:
def exist(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, index):
if index == len(word):
return True
if (r < 0 or c < 0 or r >= rows or c >= cols or
board[r][c] != word[index]):
return False
temp = board[r][c]
board[r][c] = '#' # Помечаем
found = (dfs(r + 1, c, index + 1) or
dfs(r - 1, c, index + 1) or
dfs(r, c + 1, index + 1) or
dfs(r, c - 1, index + 1))
board[r][c] = temp # Восстанавливаем
return found
for i in range(rows):
for j in range(cols):
if dfs(i, j, 0):
return True
return FalseОбъяснение:
Сложность: O(m × n × 4^L)
| Задача | Ключевая идея |
|---|---|
| Number of Islands | DFS для каждой '1', mark as '0' |
| Max Area | DFS возвращает площадь |
| Word Search | Mark/restore с '#' |
# ❌ Неправильно
board[r][c] = '#'
found = dfs(r + 1, c, index + 1)
# Забыли восстановить!
# ✅ Правильно
temp = board[r][c]
board[r][c] = '#'
found = dfs(r + 1, c, index + 1)
board[r][c] = temp# ❌ Неправильно
if index == len(word) - 1: # Не доходит до последнего символа!
# ✅ Правильно
if index == len(word): # Все символы найденыDFS: Задачи на сетках — обход сеток с mark/restore.
Ключевые приёмы:
Далее: DFS: Графы