Задача: 200. Number of Islands
Сложность: medium

Дана двумерная бинарная сетка размером 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

👨‍💻 Алгоритм:

1⃣Линейно просканируйте двумерную карту, если узел содержит '1', то это корневой узел, который запускает поиск в глубину (DFS).

2⃣Во время выполнения DFS каждый посещённый узел следует установить в '0', чтобы пометить его как посещённый.

3⃣Подсчитайте количество корневых узлов, запускающих DFS. Это количество будет равно количеству островов, так как каждый DFS, начинающийся с какого-либо корня, идентифицирует остров.

😎 Решение:

class Solution {
    private function dfs(&$grid, $r, $c) {
        $nr = count($grid);
        $nc = count($grid[0]);

        if ($r < 0 || $c < 0 || $r >= $nr || $c >= $nc || $grid[$r][$c] == '0') {
            return;
        }

        $grid[$r][$c] = '0';
        $this->dfs($grid, $r - 1, $c);
        $this->dfs($grid, $r + 1, $c);
        $this->dfs($grid, $r, $c - 1);
        $this->dfs($grid, $r, $c + 1);
    }

    public function numIslands($grid) {
        if (empty($grid)) {
            return 0;
        }

        $nr = count($grid);
        $nc = count($grid[0]);
        $numIslands = 0;

        for ($r = 0; $r < $nr; ++$r) {
            for ($c = 0; $c < $nc; ++$c) {
                if ($grid[$r][$c] == '1') {
                    $numIslands++;
                    $this->dfs($grid, $r, $c);
                }
            }
        }

        return $numIslands;
    }
}

Ставь 👍 и забирай 📚 Базу знаний