Задача: 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 {
    func dfs(_ grid: inout [[Character]], _ r: Int, _ c: Int) {
        let nr = grid.count
        let nc = grid[0].count

        if r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == "0" {
            return
        }

        grid[r][c] = "0"
        dfs(&grid, r - 1, c)
        dfs(&grid, r + 1, c)
        dfs(&grid, r, c - 1)
        dfs(&grid, r, c + 1)
    }

    func numIslands(_ grid: [[Character]]) -> Int {
        var grid = grid
        if grid.isEmpty {
            return 0
        }

        let nr = grid.count
        let nc = grid[0].count
        var numIslands = 0

        for r in 0..<nr {
            for c in 0..<nc {
                if grid[r][c] == "1" {
                    numIslands += 1
                    dfs(&grid, r, c)
                }
            }
        }

        return numIslands
    }
}

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