Leetcode 1254. Number of Closed Islands

https://leetcode.com/problems/number-of-closed-islands/description/

Notes:

The question can be viewed as a follow-up of the Number of Islands. For this one, we need to check the neighbors of the most out layer of the island. If one of them is boundary, it is not a closed island.

So we can do this in a BFS naturally, since BFS expands layer-by-layer gradually.

See the code below:

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int res = 0;
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> visit(m, vector<int>(n, 0));//not needed if we can modify grid' values
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(grid[i][j] == 0 && !visit[i][j]) {
                    bfs(grid, i, j, visit, res);
                }
            }
        }
        return res;
    }

private:
    void bfs(vector<vector<int>>& gd, int x, int y, vector<vector<int>>& visit, int &res) {
        queue<pair<int, int>> q;
        q.push({x, y});
        visit[x][y] = 1;
        vector<int> dirs = {-1, 0, 1, 0, -1};
        bool ed = false;//this is the only difference
        while(q.size()) {
            auto t = q.front();
            q.pop();
            for(int i=0; i+1<dirs.size(); ++i) {
                int a = t.first + dirs[i], b = t.second + dirs[i+1];
                if(a<0 || a>= gd.size() || b<0 || b>=gd[0].size()) {
                    ed = true;//is edge
                    continue;
                }
                if(visit[a][b] || gd[a][b]) continue;
                q.push({a, b});
                visit[a][b] = 1;
            }
        }
        if(!ed) ++res;
    }
};