---
round: 3
ticket_no: 9
source_no: 22
slug: number-of-islands
topic: DFS / BFS
difficulty: Medium
leetcode_id: 200
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 09 — Number of Islands

## Условие (как предъявлено)

Дана двумерная сетка `grid` размером `m × n`, где каждая ячейка содержит `'1'` (земля) или `'0'` (вода). Посчитайте количество островов. Остров — это группа соседних ячеек `'1'`, соединённых по горизонтали или вертикали, окружённых водой.

```
Input:  grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]  →  Output: 1

Input:  grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]  →  Output: 3
```

Constraints: `1 <= m, n <= 300`.

## Ответ

> Здесь мы обходим каждую ячейку. Если мы встречаем сушу, то мы прибавляем число островов на единицу и значит должны пройтись влево-вправо-вверх-вниз — то есть рекурсивно жадно, пока мы идём и соседей тоже земля, заменить их на воду. То есть таким образом мы как бы остров топим. И как потопили, то есть дальше уже соседей по вертикали, по горизонтали нету. Значит, мы тогда продолжаем своё путешествие по локациям. Мы дальше ищем следующую землю. Таким образом, мы гарантированно один остров только один раз учитываем.

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

**Критерии:** идея ⚠️ · структура данных ⚠️ · сложность ⚠️ · граничные случаи ⚠️

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

**Разбор задачи:** [`../../algo-solutions/02-extra/02-dfs-bfs/22-number-of-islands.md`](../../algo-solutions/02-extra/02-dfs-bfs/22-number-of-islands.md)