---
round: 1
ticket_no: 22
source_no: 22
slug: number-of-islands
topic: DFS / BFS
difficulty: Medium
leetcode_id: 200
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-12
---

# Билет 22 — Number of Islands

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

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

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

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

## Ответ

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

## Разбор

**Что верно:** скан сетки, на первой '1' инкремент счётчика и заливка острова по четырём направлениям с пометкой посещённого, затем продолжение скана — эталонная идея; отдельно отмечено, что вход можно не портить.

**Что упущено и ошибки:** не названа сложность O(m·n); не названа практическая ловушка Ruby: рекурсивный DFS падает по глубине стека (~12 000 кадров), а остров на сетке 300×300 может быть больше — на интервью нужно сразу предлагать итеративный DFS со стеком или BFS с очередью; граничные случаи (1×1, все нули, все единицы).

**Эталонная идея:** обход сетки; на '1' count += 1 и flood fill (итеративно) с заменой '1' → '0'.

**Сложность:** время O(m·n), память O(m·n) для рекурсии или O(min(m, n)) для BFS

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


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