<p>You are given an <code>m x n</code> binary matrix <code>grid</code>. An island is a group of <code>1</code>&#39;s (representing land) connected <strong>4-directionally</strong> (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.</p>

<p>The <strong>area</strong> of an island is the number of cells with a value <code>1</code> in the island.</p>

<p>Return <em>the maximum <strong>area</strong> of an island in </em><code>grid</code>. If there is no island, return <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/01/maxarea1-grid.jpg" style="width: 500px; height: 310px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
<strong>Output:</strong> 6
<strong>Explanation:</strong> The answer is not 11, because the island must be connected 4-directionally.
</pre>

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

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

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

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 50</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class Solution {
public:
    typedef pair<int, int> pos;
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int nrows = grid.size();
        int ncols = grid[0].size();
        int area = 0;
        int max_area = 0;

        if (!nrows && ncols)
            return max_area;
        
        for (int i = 0; i < nrows; ++i) {
            for (int j = 0; j < ncols; ++j) {

                // skip all water cells and already visited ones
                if (!grid[i][j])
                    continue;
                // get the area of an island
                area = bfs(grid, i, j);
                max_area = max(max_area, area);
            }
        }
        return max_area;
    }

    int bfs(vector<vector<int>> &grid, int row, int col) {

        int area = 0;
        queue<pos> q;
        vector<pos> neighbors;
        pos p = {row, col};
        int c_row = 0, c_col = 0;

        q.push(p);
        // mark the current cell visited
        grid[row][col] = 0;
        ++area;

        while(!q.empty()) {
            
            // no to eed of keep track of levels; just tx graph fully
            pos cell = q.front();
            q.pop();

            get_valid_neighbors(grid, cell, neighbors);
            
            for (int i = 0; i < neighbors.size(); ++i) {
                p = neighbors[i];

                //if (!grid[p.first][p.second])
                //    continue;

                // each cell we here is a valid cell
                ++area;
                q.push(p);
                grid[p.first][p.second] = 0;
            }
            neighbors.clear();
        }
        return area;
    }

    void get_valid_neighbors(vector<vector<int>> &grid, pos cell, vector<pos> &neighbors) {

        // only 4 directions; no diagonal checks
        vector<int> x = {-1, 0, 1, 0};
        vector<int> y = {0, 1, 0, -1};  
        int dx = 0, dy = 0;

        for(int i = 0; i < x.size(); ++i) {

            dx = cell.first + x[i];
            dy = cell.second + y[i];

            // check if dx and dy are within the bounds of the grid
            if (dx >= 0 && dx < grid.size() && dy >=0 && dy < grid[0].size()) {

                // check if the cell is valid; 0 NO 1 yes
                if (!grid[dx][dy])
                    continue; // water cell or the already visited ones
                
                neighbors.push_back({dx, dy});
            }
        }
    }
};
33810