1254. Number of Closed Islands

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

• bfs solution

c++

class Solution {
    void bfs(vector<vector<int>>& grid, int cy, int cx) {
        int n = grid.size(), m = grid[0].size();
        int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};
        queue<pair<int,int>> q;
        q.push({cy,cx});
        grid[cy][cx] = 1;
        while(!q.empty()) {
            auto [y, x] = q.front(); q.pop();
            for(int i = 0; i < 4; i++) {
                int ny = y + dy[i], nx = x + dx[i];
                if(0 <= nx and nx < m and 0 <= ny and ny < n and !grid[ny][nx]) {
                    q.push({ny,nx});
                    grid[ny][nx] = 1;
                }
            }
        }
    }
public:
    int closedIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        for(int i = 0; i < m; i++) {
            if(!grid[0][i]) bfs(grid, 0, i);
            if(!grid[n-1][i]) bfs(grid, n-1, i);
        }
        for(int i = 0; i < n; i++) {
            if(!grid[i][0]) bfs(grid,i,0);
            if(!grid[i][m-1]) bfs(grid,i,m-1);
        }
        
        int res = 0;
        for(int i = 1; i < n - 1; i++) {
            for(int j = 1; j < m - 1; j++) {
                if(!grid[i][j]) {
                    bfs(grid,i,j);
                    res++;
                }
            }
        }
        
        return res;
    }
};

• flood fill solution

c++

class Solution {
    int floodfill(vector<vector<int>>& grid, int y, int x) {
        if(0 <= y and y < grid.size() and 0 <= x and x < grid[y].size() and grid[y][x] == 0) {
            return (grid[y][x] = 1) + floodfill(grid, y - 1, x) + floodfill(grid, y + 1, x) + floodfill(grid, y, x + 1) + floodfill(grid, y , x - 1);
        }
        return 0;
    }
public:
    int closedIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        for(int i = 0; i < m; i++) {
            if(!grid[0][i]) floodfill(grid, 0, i);
            if(!grid[n-1][i]) floodfill(grid, n-1, i);
        }
        for(int i = 0; i < n; i++) {
            if(!grid[i][0]) floodfill(grid,i,0);
            if(!grid[i][m-1]) floodfill(grid,i,m-1);
        }
        
        int res = 0;
        for(int i = 1; i < n - 1; i++) {
            for(int j = 1; j < m - 1; j++) {
                if(!grid[i][j]) {
                    floodfill(grid,i,j);
                    res++;
                }
            }
        }
        
        return res;
    }
};