Surrounded Regions

Средняя№130сетка

Дана доска из X и O. Группа клеток O, связанных сторонами, окружена, если ни одна из них не лежит на краю доски; каждую окружённую O нужно заменить на X прямо на доске. На нашей доске 4 строки: X X X X X, X O X O X, X O X O O, X X O X X — ответ X X X X X, X X X O X, X X X O O, X X O X X: две O слева окружены, три справа выходят на край в (2, 4), а (3, 2) сама лежит на краю.

130 Surrounded RegionsРазбор · 1×

Пример: заменить окружённые O на доске, начав обход с её края.

012340123XXXXXXOXOXXOXOOXXOXXстек вызововвершина справа—
O, от края не дошлиX или O, заменённая на Xв стеке вызововтекущая клеткасоседняя O, её сохраняем следующейсвязана с краем: K, потом снова O

Сначала край: O на нём окружить нельзя, как и любую O, связанную с ней

01/37
сначала · назад · пуск · шаг
Скорость
1function solve(board):
2 for each cell (row, col) on the border:
3 if board[row][col] == 'O':
4 keep(row, col)
5 for each cell (row, col) in board:
6 if board[row][col] == 'O':
7 board[row][col] = 'X' // surrounded
8 else if board[row][col] == 'K':
9 board[row][col] = 'O' // joined to the border
10 return board
11
12function keep(r, c):
13 board[r][c] = 'K'
14 for each neighbour (nr, nc) that is 'O':
15 keep(nr, nc)
состояние
row
–
col
–
r
–
c
–
nr
–
nc
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. O в безопасности ровно тогда, когда она связана с O на краю, поэтому обход от O на краю помечает все такие O и только их.
  2. Проверять каждую O отдельно — значит искать заново для каждой клетки; один обход от края решает всё сразу.
  3. Пометка K не даёт обходу зайти в клетку дважды и подсказывает второму проходу, какие O оставить.

Сложность

Время O(rows × cols): keep входит в каждую клетку не больше одного раза, а второй проход смотрит на каждую клетку один раз. Память O(rows × cols) в худшем случае — на стек вызовов.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.