Number of Islands

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

Дана карта из клеток суши и воды. Клетки суши, которые касаются стороной, — один остров; касание углом не считается. Нужно посчитать острова. На нашей карте 4 строки: # . # ., # . # ., # # # ., . . . # (# — суша) — ответ 2: первые семь клеток суши образуют один остров в форме буквы U, а клетка в правом нижнем углу — отдельно.

200 Number of IslandsРазбор · 1×

Пример: посчитать острова на карте, где один остров загибается обратно вверх, а одна клетка касается его только углом.

01230123~~~~~~~~стек вызововвершина справа—
суша, ещё не в seenводав стеке вызововтекущая клеткасоседняя суша, обходим следующейв seen, внутри — номер острова

seen пуст: ни одной клетки ещё не посетили

01/51
сначала · назад · пуск · шаг
Скорость
1function numIslands(grid):
2 seen = empty set
3 islands = 0
4 for each cell (row, col), row by row:
5 if grid[row][col] is land and (row, col) not in seen:
6 islands = islands + 1
7 explore(row, col)
8 return islands
9
10function explore(r, c):
11 seen.add((r, c))
12 for each land neighbour (nr, nc) not in seen:
13 explore(nr, nc)
состояние
islands
–
row
–
col
–
r
–
c
–
nr
–
nc
–
нажмите шаг, чтобы вернуться

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

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

  1. explore добавляет в seen каждую клетку суши, до которой можно дойти через стороны, в любую сторону, в том числе вверх. Поэтому один вызов охватывает весь остров, как бы он ни изгибался.
  2. Проход начинает новый остров только на суше, которой ещё нет в seen, поэтому каждый остров считается один раз: на его первой клетке по строкам.
  3. Каждая клетка суши попадает в seen один раз, и explore запускается на ней один раз, поэтому обход не зацикливается.

Сложность

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

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

Решить на LeetCode ↗

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