---
title: Number of Islands
difficulty: Medium
category: DFS / BFS
leetcode_id: 200
revision_count: 1
last_revision: 2026-09-12
---

# Number of Islands

> **LeetCode:** [#200](https://leetcode.com/problems/number-of-islands/)
> **Сложность:** Medium
> **Категория:** DFS / BFS

## Условие

Дана двумерная сетка `grid` размером `m x 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']
]  →  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
```

## Ключевая идея

Обходим все клетки сетки. При встрече `'1'` увеличиваем счётчик и «затапливаем» (flood-fill) весь остров DFS/BFS, превращая все его единицы в нули. Так каждый остров будет учтён ровно один раз, и повторные обходы его не найдут.

## Оценка сложности

- **Время:** O(m × n) — каждая клетка посещается не более одного раза
- **Память:** O(m × n) в худшем случае — глубина рекурсии при DFS (если вся сетка — один остров). В Ruby рекурсия падает примерно на 12 000 кадрах стека, поэтому на большом острове её заменяют на итеративный DFS/BFS (см. «Типичные ошибки» и `22-sandbox.rb`). BFS через очередь даёт O(min(m, n)). Union-Find — O(m × n) на массив родителей.

## Решение (Ruby)

```ruby
# @param {Character[][]} grid
# @return {Integer}
def num_islands(grid)
  return 0 if grid.empty?

  m, n = grid.size, grid[0].size
  count = 0

  dfs = lambda do |i, j|
    return if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1'

    grid[i][j] = '0'  # топим клетку — помечаем посещённой
    dfs.call(i + 1, j)
    dfs.call(i - 1, j)
    dfs.call(i, j + 1)
    dfs.call(i, j - 1)
  end

  (0...m).each do |i|
    (0...n).each do |j|
      next unless grid[i][j] == '1'

      count += 1
      dfs.call(i, j)
    end
  end

  count
end
```

### BFS-вариант (на случай, если спросят про stack overflow)

```ruby
# @param {Character[][]} grid
# @return {Integer}
def num_islands(grid)
  return 0 if grid.empty?

  m, n = grid.size, grid[0].size
  count = 0
  dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]

  (0...m).each do |i|
    (0...n).each do |j|
      next unless grid[i][j] == '1'

      count += 1
      queue = [[i, j]]
      grid[i][j] = '0'

      until queue.empty?
        r, c = queue.shift
        dirs.each do |dr, dc|
          nr, nc = r + dr, c + dc
          next if nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] != '1'

          grid[nr][nc] = '0'
          queue << [nr, nc]
        end
      end
    end
  end

  count
end
```

## OOP-вариант: DFS и BFS отдельными стратегиями

Запускаемый код с проверками → `22-sandbox.rb` (`ruby 22-sandbox.rb`). Роли классов:

- **`Grid`** — данные + поведение: знает свои размеры, отвечает `land?(row, col)`, умеет `sink!(row, col)` и обход клеток земли `each_land_cell`. Стратегии больше не знают ни про `'1'`/`'0'`, ни про границы — вся валидация индексов живёт в одном месте.
- **`FloodFills::Base` + `Dfs` / `IterativeDfs` / `Bfs`** — паттерн **Strategy**. Один контракт: `call(grid, row, col)` — затопить остров, которому принадлежит клетка.
- **`Counter`** — контекст: проходит по земле, делегирует обход вложенной стратегии (injection через конструктор). Ему безразлично, каким обходом его снабдили.
- **`num_islands(grid, flood_fill:)`** — LeetCode-совместимая обёртка, по умолчанию `Dfs`.

```ruby
module NumberOfIslands
  LAND = '1'
  WATER = '0'
  NEIGHBOURS = [[-1, 0], [1, 0], [0, -1], [0, 1]].freeze

  class Grid
    attr_reader :rows, :cols

    # copy: true — входную матрицу не портим, но платим +O(rows*cols) памяти.
    # В интервью обычно ждут in-place (copy: false) — тогда память O(1) плюс стек/очередь.
    def initialize(matrix, copy: true)
      @cells = copy ? matrix.map(&:dup) : matrix
      @rows = @cells.size
      @cols = rows.zero? ? 0 : @cells.first.size
    end

    def land?(row, col)
      in_bounds?(row, col) && @cells[row][col] == LAND
    end

    def sink!(row, col)
      @cells[row][col] = WATER
    end

    def each_land_cell
      return to_enum(:each_land_cell) unless block_given?

      rows.times do |r|
        cols.times { |c| yield r, c if land?(r, c) }
      end
    end

    private

    def in_bounds?(row, col)
      row >= 0 && row < rows && col >= 0 && col < cols
    end
  end

  module FloodFills
    class Base
      def call(grid, row, col)
        raise NotImplementedError, "#{self.class} must implement #call(grid, row, col)"
      end
    end

    class Dfs < Base
      def call(grid, row, col)
        return unless grid.land?(row, col)

        grid.sink!(row, col)
        NEIGHBOURS.each { |dr, dc| call(grid, row + dr, col + dc) }
      end
    end

    class IterativeDfs < Base
      def call(grid, row, col)
        return unless grid.land?(row, col)

        stack = [[row, col]]
        grid.sink!(row, col)
        until stack.empty?
          r, c = stack.pop
          NEIGHBOURS.each do |dr, dc|
            nr = r + dr
            nc = c + dc
            next unless grid.land?(nr, nc)

            grid.sink!(nr, nc)
            stack << [nr, nc]
          end
        end
      end
    end

    class Bfs < Base
      def call(grid, row, col)
        return unless grid.land?(row, col)

        queue = [[row, col]]
        grid.sink!(row, col)
        head = 0 # вместо queue.shift (O(n) на каждом шаге)
        while head < queue.size
          r, c = queue[head]
          head += 1
          NEIGHBOURS.each do |dr, dc|
            next unless grid.land?(r + dr, c + dc)

            grid.sink!(r + dr, c + dc)
            queue << [r + dr, c + dc]
          end
        end
      end
    end
  end

  class Counter
    def initialize(flood_fill: FloodFills::Dfs.new)
      @flood_fill = flood_fill
    end

    def call(matrix)
      grid = Grid.new(matrix)
      count = 0
      grid.each_land_cell do |row, col|
        count += 1
        @flood_fill.call(grid, row, col)
      end
      count
    end
  end

  def self.solve(matrix, flood_fill: FloodFills::Dfs.new)
    Counter.new(flood_fill: flood_fill).call(matrix)
  end
end

def num_islands(grid, flood_fill: NumberOfIslands::FloodFills::Dfs.new)
  NumberOfIslands.solve(grid, flood_fill: flood_fill)
end
```

```ruby
num_islands(grid)                                                       # DFS по умолчанию
num_islands(grid, flood_fill: NumberOfIslands::FloodFills::Bfs.new)     # BFS
num_islands(grid, flood_fill: NumberOfIslands::FloodFills::IterativeDfs.new)
```

Когда так писать, а когда нет:

- **На интервью** — сначала простое решение на 5 строк; ООП-версия нужна, если разговор ушёл в дизайн («как переиспользовать flood fill для других задач?» — заливка картинки, поиск компонент, проверка связности).
- **В продакшене** — оправдано: flood fill нужен и в других задачах, поэтому его переиспользуют, не переписывая проверки границ каждый раз.
- **Минус** — 120 строк против 20 и лишний indirection. Если задача одноразовая — это over-engineering, честно так и сказать.

## Разбор на примере

```
Input: grid = [
  ['1','1','0'],
  ['1','0','0'],
  ['0','0','1']
]

  i=0,j=0: grid[0][0] == '1' → count=1, запускаем DFS
    DFS(0,0): топим → grid[0][0]='0', идём вниз(1,0), вверх(-1,0) — выход,
              вправо(0,1), влево(0,-1) — выход
    DFS(1,0): топим → grid[1][0]='0', идём вниз(2,0) — 0, проход,
              вверх(0,0) — уже '0', вправо(1,1) — 0, проход, влево(1,-1) — выход
    DFS(0,1): топим → grid[0][1]='0', соседи все '0' или выход

  i=0,j=1: grid[0][1] == '0' → пропускаем
  i=0,j=2: '0' → пропускаем
  i=1,j=0: '0' → пропускаем
  i=1,j=1: '0' → пропускаем
  i=1,j=2: '0' → пропускаем
  i=2,j=0: '0' → пропускаем
  i=2,j=1: '0' → пропускаем
  i=2,j=2: grid[2][2] == '1' → count=2, запускаем DFS
    DFS(2,2): топим, соседи все '0' или выход

Result: 2 острова
```

## Edge Cases

- **Пустая сетка**: `grid = []` → сразу возвращаем 0.
- **Одна строка / один столбец**: `[['1','0','1']]` → считаем корректно, рекурсия/очередь не выходят за границы.
- **Вся вода**: `[['0','0'],['0','0']]` → 0 островов.
- **Вся земля**: `[['1','1'],['1','1']]` → 1 остров.
- **Диагональные соседи не считаются**: `[['1','0'],['0','1']]` → 2 острова (не соединены).
- **Сетка 1×1**: `[['1']]` → 1 остров; `[['0']]` → 0.

## Типичные ошибки

1. ❌ **Забыть проверку границ перед обращением к сетке** — `i < 0 || i >= m` и т.д. При recursive DFS без этого — `IndexError`.
2. ❌ **Не мутировать сетку (или не использовать visited)** — без маркировки посещённых клеток DFS зациклится или будет бесконечно обходить один и тот же остров.
3. ❌ **Считать диагонали соседями** — условие задачи: только 4 направления (вверх/вниз/влево/вправо). Диагонали не соединяют острова.
4. ❌ **BFS с `Array#shift` на больших данных** — `shift` — O(n) для массива. Для интервью сойдёт, но если размер сетки большой — лучше использовать очередь с указателем (или `deque`). Ponytail: `queue.shift` O(n) — заменить на `deque` из `algorithms` gem или на очередь через два стека, когда production.
5. ❌ **Рекурсивный DFS без плана Б на большой остров** — глубина рекурсии равна размеру острова. Замерено локально (Ruby 4.0.2): стек ломается примерно на **11 900 кадрах**, а остров «вся сетка 300×300» — это 90 000 клеток → `SystemStackError`. Проверяется запуском `22-sandbox.rb`: `iterative_dfs` и `bfs` те же 300×300 и полосу 1×200 000 проходят, рекурсивный `dfs` — нет. На интервью: назвать рекурсивный DFS, но сразу добавить, что при большом острове перехожу на итеративный DFS или BFS.

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| **DFS (рекурсивный)** | **O(m·n)** | **O(m·n)** | **Принято на интервью** — лаконично, читаемо |
| BFS (очередь) | O(m·n) | O(min(m, n)) | Безопаснее по стеку, но больше кода |
| Union-Find (DSU) | O(m·n·α) | O(m·n) | Избыточен для этой задачи, но полезен, если острова динамически объединяются |
| **DFS итеративный (стек)** | **O(m·n)** | **O(m·n)** | **Безопасная альтернатива** рекурсии — тот же DFS, но без риска stack overflow |

Рекурсивный DFS — самый простой и читаемый вариант для интервью. Если интервьюер упрётся в stack overflow — переключаемся на BFS или итеративный DFS.

## Заметки после повторения

_— Заполняется после каждой тренировки._