<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>

    /*
    Input: grid = 
    [
        [0,0,1,1,0,1,0,0,1,0],
        [1,1,0,1,1,0,1,1,1,0],
        [1,0,1,1,1,0,0,1,1,0],
        [0,1,1,0,0,0,0,1,0,1],
        [0,0,0,0,0,0,1,1,1,0],
        [0,1,0,1,0,1,0,1,1,1],
        [1,0,1,0,1,1,0,0,0,1],
        [1,1,1,1,1,1,0,0,0,0],
        [1,1,1,0,0,1,0,1,0,1],
        [1,1,1,0,1,1,0,1,1,0]
    ]
    */
class Solution {
private:
    int ROWS;
    int COLS;

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

    bool is_valid(int i, int j) {
        return i > -1 && j > -1 && i < ROWS && j < COLS;
    }

    bool is_edge(int i, int j) {
        return i == 0 || j == 0 || i == ROWS - 1 || j == COLS - 1;
    }

    int bfs(vector<vector<int>>& grid, vector<vector<int>>& seen, int i, int j) {
        queue<vector<int>> q;

        bool edge = false;

        if (is_edge(i, j)) edge = true;

        seen[i][j] = 1;

        q.push({i, j});


        while (!q.empty()) {
            vector<int> curr = q.front(); q.pop();
            int row = curr[0], col = curr[1];

            if (is_edge(row, col)) edge = true;

            for (vector<int> direction : directions) {
                int row_next = row + direction[0];
                int col_next = col + direction[1];

                if (is_valid(row_next, col_next) && !seen[row_next][col_next] && grid[row_next][col_next] == 0) {
                        seen[row_next][col_next] = 1;
                    q.push({row_next, col_next});
                }
            }
        }

        return !edge;
    }


public:
    int closedIsland(vector<vector<int>>& grid) {
        vector<vector<int>> seen(grid.size(), vector<int>(grid[0].size(), 0));
        
        int ans = 0;
        ROWS = grid.size();
        COLS = grid[0].size();

        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                if (grid[i][j] == 0 && !seen[i][j] && !is_edge(i, j)) {
                    ans += bfs(grid, seen, i, j);
                }
            }
        }

        return ans;
    }
};
23180