<p>You are given a <strong>0-indexed</strong> <code>m x n</code> binary matrix <code>land</code> where a <code>0</code> represents a hectare of forested land and a <code>1</code> represents a hectare of farmland.</p>

<p>To keep the land organized, there are designated rectangular areas of hectares that consist <strong>entirely</strong> of farmland. These rectangular areas are called <strong>groups</strong>. No two groups are adjacent, meaning farmland in one group is <strong>not</strong> four-directionally adjacent to another farmland in a different group.</p>

<p><code>land</code> can be represented by a coordinate system where the top left corner of <code>land</code> is <code>(0, 0)</code> and the bottom right corner of <code>land</code> is <code>(m-1, n-1)</code>. Find the coordinates of the top left and bottom right corner of each <strong>group</strong> of farmland. A <strong>group</strong> of farmland with a top left corner at <code>(r<sub>1</sub>, c<sub>1</sub>)</code> and a bottom right corner at <code>(r<sub>2</sub>, c<sub>2</sub>)</code> is represented by the 4-length array <code>[r<sub>1</sub>, c<sub>1</sub>, r<sub>2</sub>, c<sub>2</sub>].</code></p>

<p>Return <em>a 2D array containing the 4-length arrays described above for each <strong>group</strong> of farmland in </em><code>land</code><em>. If there are no groups of farmland, return an empty array. You may return the answer in <strong>any order</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/27/screenshot-2021-07-27-at-12-23-15-copy-of-diagram-drawio-diagrams-net.png" style="width: 300px; height: 300px;" />
<pre>
<strong>Input:</strong> land = [[1,0,0],[0,1,1],[0,1,1]]
<strong>Output:</strong> [[0,0,0,0],[1,1,2,2]]
<strong>Explanation:</strong>
The first group has a top left corner at land[0][0] and a bottom right corner at land[0][0].
The second group has a top left corner at land[1][1] and a bottom right corner at land[2][2].
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/27/screenshot-2021-07-27-at-12-30-26-copy-of-diagram-drawio-diagrams-net.png" style="width: 200px; height: 200px;" />
<pre>
<strong>Input:</strong> land = [[1,1],[1,1]]
<strong>Output:</strong> [[0,0,1,1]]
<strong>Explanation:</strong>
The first group has a top left corner at land[0][0] and a bottom right corner at land[1][1].
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/27/screenshot-2021-07-27-at-12-32-24-copy-of-diagram-drawio-diagrams-net.png" style="width: 100px; height: 100px;" />
<pre>
<strong>Input:</strong> land = [[0]]
<strong>Output:</strong> []
<strong>Explanation:</strong>
There are no groups of farmland.
</pre>

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

<ul>
	<li><code>m == land.length</code></li>
	<li><code>n == land[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>land</code> consists of only <code>0</code>&#39;s and <code>1</code>&#39;s.</li>
	<li>Groups of farmland are <strong>rectangular</strong> in shape.</li>
</ul>

class Solution {
public:
    int m;
    int n;
    vector<vector<int>> directions{
        {1,0},
        {-1,0},
        {0,1},
        {0,-1}
    };

    //FUNCTION FOR DFS:
    void dfs(vector<vector<int>>& land,int i,int j,int& r2,int& c2)
    {
        if (i < 0 || i >= m || j < 0 || j >= n || land[i][j] == 0) {
            return;
        }

        land[i][j] = 0;

        r2 = max(r2,i);
        c2 = max(c2,j);

        dfs(land,i+1,j,r2,c2);
        dfs(land,i-1,j,r2,c2);
        dfs(land,i,j+1,r2,c2);
        dfs(land,i,j-1,r2,c2);
    }

    //FUNCTION FOR BFS:
    void bfs(vector<vector<int>>& land,int i,int j,int& r2,int& c2)
    {
        queue<pair<int,int>> q;
        q.push({i,j});

        while(!q.empty())
        {
            auto frontNode = q.front();
            q.pop();

            r2 = max(r2,frontNode.first);
            c2 = max(c2,frontNode.second);

            for(auto& dir:directions)
            {
                int i_ = frontNode.first + dir[0];
                int j_ = frontNode.second + dir[1];

                if(i_>=0 && i_<m && j_>=0 && j_<n && land[i_][j_]==1)
                {
                    land[i_][j_]=0;
                    q.push({i_,j_});
                }
            }
        }
    }



    vector<vector<int>> findFarmland(vector<vector<int>>& land) {
        //APPROACH 1: {DFS}:
        // m = land.size();
        // n = land[0].size();
        // vector<vector<int>> ans;

        // for(int i=0;i<m;i++)
        // {
        //     for(int j=0;j<n;j++)
        //     {
        //         if(land[i][j]==1)
        //         {
        //             int r1 = i;
        //             int c1 = j;
        //             int r2 = -1;
        //             int c2 = -1;
        //             dfs(land,r1,c1,r2,c2);
        //             ans.push_back({r1,c1,r2,c2});
        //         }
        //     }
        // }
        // return ans;


        //APPROACH 2: {BFS}:
        m = land.size();
        n = land[0].size();
        vector<vector<int>> ans;

        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(land[i][j]==1)
                {
                    int r1 = i;
                    int c1 = j;
                    int r2 = -1;
                    int c2 = -1;
                    bfs(land,r1,c1,r2,c2);
                    ans.push_back({r1,c1,r2,c2});
                }
            }
        }
        return ans;
    }
};
137528