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

    int dx[4] = {-1, 0, 0, 1};
    int dy[4] = {0, -1, 1, 0};
    int sz_fix;
    int bfs(queue<pair<int, int>> &q, vector<vector<bool >> &visit, vector<vector<int>> &mat){
        int sz = INT_MIN;
        // auto pr_temp = q.front();
        // sz_fix = pr_temp.first;
        while(!q.empty()){
            auto temp = q.front();
            q.pop();

            int i = temp.first, j = temp.second;
            visit[i][j] = true;

            for(int k = 0; k < 4; k++){
            int ti = i + dx[k], tj = j + dy[k];
                if(ti >= 0 && tj >= 0 && ti < mat.size() && tj < mat[0].size() && visit[ti][tj] == false && mat[ti][tj] == 1){
                    temp = make_pair(ti, tj);
                    sz_fix++;
                    q.push(temp);
                    visit[ti][tj] = true;
                }
            }
        }
        sz = max(sz, sz_fix);
        return sz;
    }

    int maxAreaOfIsland(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();

        vector<vector<bool >> visit(m, vector<bool >(n, false));
        pair<int, int> pr;

        queue<pair<int, int>> q;
        int ans = INT_MIN;
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){

                if(mat[i][j] == 1 && visit[i][j] == false){
                    sz_fix = 1;
                    pr =  make_pair(i, j);
                    q.push(pr);
                    ans = max(ans, bfs(q, visit, mat));
                }
            }
        }

        if(ans == INT_MIN) return 0;
        
        return ans;
    }
};
29330