Задача: 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, начинающийся с какого-либо корня, идентифицирует остров.

😎 Решение:

public class Solution {
    private void Dfs(char[][] grid, int r, int c) {
        int nr = grid.Length;
        int nc = grid[0].Length;

        grid[r][c] = '0';
        if (r - 1 >= 0 && grid[r - 1][c] == '1') Dfs(grid, r - 1, c);
        if (r + 1 < nr && grid[r + 1][c] == '1') Dfs(grid, r + 1, c);
        if (c - 1 >= 0 && grid[r][c - 1] == '1') Dfs(grid, r, c - 1);
        if (c + 1 < nc && grid[r][c + 1] == '1') Dfs(grid, r, c + 1);
    }

    public int NumIslands(char[][] grid) {
        int nr = grid.Length;
        if (nr == 0) return 0;
        int nc = grid[0].Length;

        int numIslands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    numIslands++;
                    Dfs(grid, r, c);
                }
            }
        }

        return numIslands;
    }
}

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