1254. Number of Closed Islands

leetcode medium

#array#csharp#graph#leetcode#linked-list#matrix#medium#search

Task

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

C# solution

matched/original

public class Solution {
    public int ClosedIsland(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 0) {
                    Dfs(grid, i, j);
                }
            }
        }
        int count = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 0) {
                    Dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void Dfs(int[][] grid, int x, int y) {
        if (x < 0 || y < 0 || x >= grid.Length || y >= grid[0].Length || 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);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ClosedIsland(int[][] grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 0) {
                    Dfs(grid, i, j);
                }
            }
        }
        int count = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 0) {
                    Dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void Dfs(int[][] grid, int x, int y) {
        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);
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int ClosedIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 0) {
                    Dfs(grid, i, j);
                }
            }
        }
        int count = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 0) {
                    Dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void Dfs(int[][] grid, int x, int y) {
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || 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);
    }
}

Explanation

Algorithm

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

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

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

😎