Осушение замкнутых прудов

Средняя

Карта местности задана таблицей grid размером m × n: 'X' — суша, 'O' — вода. Клетки воды, соседние по горизонтали или вертикали, образуют один пруд. Пруд, ни одна клетка которого не лежит на краю карты, считается замкнутым — вода из него никуда не уходит. Осушите все замкнутые пруды: замените их клетки на 'X'. Пруды, касающиеся края, не трогайте. Верните карту после осушения.

Пример 1

grid=[['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'O'], ['X', 'O', 'X', 'X'], ['X', 'X', 'O', 'X']] → [['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'O'], ['X', 'X', 'X', 'X'], ['X', 'X', 'O', 'X']]

Пруд из двух клеток во втором столбце со всех сторон окружён сушей и осушается. Клетка справа во второй строке и клетка внизу лежат на краю карты — они остаются водой.

Пример 2

grid=[['O', 'O', 'O'], ['O', 'X', 'O'], ['O', 'O', 'O']] → [['O', 'O', 'O'], ['O', 'X', 'O'], ['O', 'O', 'O']]

Вся вода касается края — менять нечего.

Пример 3

grid=[['X', 'X', 'X'], ['X', 'O', 'X'], ['X', 'X', 'X']] → [['X', 'X', 'X'], ['X', 'X', 'X'], ['X', 'X', 'X']]

Единственная клетка воды в центре окружена сушей и становится сушей.

Ограничения

m == grid.length, n == grid[i].length
1 ≤ m, n ≤ 200
grid[i][j] — это 'X' или 'O'

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Depth-First Search Breadth-First Search Union Find Array Matrix

Вход

grid=[['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'O'], ['X', 'O', 'X', 'X'], ['X', 'X', 'O', 'X']]

Ожидается

[['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'O'], ['X', 'X', 'X', 'X'], ['X', 'X', 'O', 'X']]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 36 тестов на сервере, включая скрытые.