<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:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        rows,cols=len(land),len(land[0])
        answer=[]

        def findbottomright(r, c):
            right=c
            while right+1<cols and land[r][right+1]==1:
                right+=1
            
            bottom=r
            while bottom+1<rows and land[bottom+1][right]==1:
                bottom+=1
            
            return bottom,right

        for r in range(rows):
            for c in range(cols):
                if land[r][c]==1:
                    if (r>0 and land[r-1][c]==1) or (c>0 and land[r][c-1]==1):
                        continue
                    bottom,right = findbottomright(r, c)
                    answer.append([r,c,bottom,right])

        return answer



# class Solution:
#     def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
#         rows,cols=len(land),len(land[0])
#         answer=[]

#         def dfs(r, c):
#             stack=deque([(r,c)])
#             maxr,maxc=r,c

#             while len(stack)!=0:
#                 row, col=stack.pop()
#                 land[row][col]=0
#                 maxr=max(maxr,row)
#                 maxc=max(maxc, col)

#                 for dr,dc in [(0,1),(1,0)]:
#                     nr,nc=row+dr,col+dc
#                     if 0<=nr<rows and 0<=nc<cols and land[nr][nc]==1:
#                         stack.append((nr,nc))

#             return [r,c,maxr,maxc]

#         for row in range(rows):
#             for col in range(cols):
#                 if land[row][col]==1:
#                     answer.append(dfs(row, col))

#         return answer



# class Solution:
#     def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
#         rows,cols=len(land),len(land[0])
#         visited=set()
#         answer=[]

#         def bfs(r,c):
#             queue=deque()
#             queue.append((r,c))
#             visited.add((r,c))
#             directions=[[1,0],[-1,0],[0,1],[0,-1]]
#             tempanswer=[r,c]

#             while len(queue)!=0:
#                 row,col=queue.popleft()
#                 for dr,dc in directions:
#                     nr,nc=row+dr,col+dc
#                     if 0<=nr<rows and 0<=nc<cols and land[nr][nc]==1 and (nr,nc) not in visited:
#                         queue.append((nr,nc))
#                         visited.add((nr,nc))


#             tempanswer.extend([row,col])
#             answer.append(tempanswer)


#         for row in range(rows):
#             for col in range(cols):
#                 if land[row][col]==1 and (row,col) not in visited:
#                     bfs(row,col)
        
#         return answer
588