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

Дана двумерная сетка, состоящая из 0 (земля) и 1 (вода).Остров - это максимальная 4-направленно связная группа из 0s, а закрытый остров - это остров, полностью (слева, сверху, справа, снизу) окруженный 1s. Верните количество закрытых островов.

Пример:

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2

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

1⃣Пройдите по границам сетки и с помощью поиска в глубину (DFS) или поиска в ширину (BFS) замените все связанные земли (0) на воду (1).

2⃣Пройдите по всей сетке, используя DFS или BFS для поиска всех оставшихся островов (групп 0)

3⃣Подсчитайте количество таких островов.

😎 Решение:

class Solution {
    fun closedIsland(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size

        for (i in grid.indices) {
            for (j in grid[0].indices) {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 0) {
                    dfs(grid, i, j)
                }
            }
        }

        var count = 0
        for (i in 1 until m - 1) {
            for (j in 1 until n - 1) {
                if (grid[i][j] == 0) {
                    dfs(grid, i, j)
                    count++
                }
            }
        }

        return count
    }

    private fun dfs(grid: Array<IntArray>, x: Int, y: Int) {
        if (x < 0 || y < 0 || x >= grid.size || y >= grid[0].size || grid[x][y] == 1) {
            return
        }
        grid[x][y] = 1
        dfs(grid, x + 1, y)
        dfs(grid, x - 1, y)
        dfs(grid, x, y + 1)
        dfs(grid, x, y - 1)
    }
}

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