<p>Given a 2D&nbsp;<code>grid</code> consists of <code>0s</code> (land)&nbsp;and <code>1s</code> (water).&nbsp; An <em>island</em> is a maximal 4-directionally connected group of <code><font face="monospace">0</font>s</code> and a <em>closed island</em>&nbsp;is an island <strong>totally</strong>&nbsp;(all left, top, right, bottom) surrounded by <code>1s.</code></p>

<p>Return the number of <em>closed islands</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/10/31/sample_3_1610.png" style="width: 240px; height: 120px;" /></p>

<pre>
<strong>Input:</strong> 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]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 
Islands in gray are closed because they are completely surrounded by water (group of 1s).</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/10/31/sample_4_1610.png" style="width: 160px; height: 80px;" /></p>

<pre>
<strong>Input:</strong> grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1,1,1,1,1,1],
&nbsp;              [1,0,0,0,0,0,1],
&nbsp;              [1,0,1,1,1,0,1],
&nbsp;              [1,0,1,0,1,0,1],
&nbsp;              [1,0,1,1,1,0,1],
&nbsp;              [1,0,0,0,0,0,1],
               [1,1,1,1,1,1,1]]
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= grid.length, grid[0].length &lt;= 100</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;=1</code></li>
</ul>

using namespace std;

class Solution {
public:
    int rows,columns;

/*    bool dfs(vector<vector<int>>& grid, int r, int c){
        
        if(r < 0 || r >= rows || c < 0 || c >= columns){
            return false;
        }

        if(grid[r][c] == 1){
            return true;
        }

        grid[r][c] = 1;

        // check all 4 sides

        bool left_closed = dfs(grid, r, c - 1);
        bool right_closed = dfs(grid, r, c + 1);
        bool up_closed = dfs(grid, r - 1, c);
        bool down_closed = dfs(grid, r + 1, c);

        return left_closed && right_closed && up_closed && down_closed;

    }

*/

bool bfs(vector<vector<int>>& grid, int r, int c){
    
    
    queue<pair<int,int>> q;
    q.push({r,c});

    bool is_closed = true;

    vector<pair<int,int>> directions = {{0,1}, {0,-1}, {1,0}, {-1,0}};

    grid[r][c] = 1;

    while(!q.empty()){
        auto [x,y] = q.front();
        q.pop();

        for(auto& [dx, dy]: directions){
            int nx = x + dx;
            int ny = y + dy;

            if(nx < 0 || nx >= rows || ny < 0 || ny >= columns ){
                is_closed = false;
            }

            else if(grid[nx][ny] == 0){
                grid[nx][ny] = 1;
                q.push({nx,ny});
            }
        }
    }
    return is_closed;
}




    int closedIsland(vector<vector<int>>& grid) {
        
        rows = grid.size();
        columns = grid[0].size();
        int count = 0;

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < columns; j++){
                if(grid[i][j] == 0){
                    if(bfs(grid, i, j) == true){
                        count++;
                    }
                }
            }
        }

        return count;
    
    }

    
};
17968