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

# 0 森林土地，1 农场

# 农场土地之间以矩形的 农场组 的形式存在。
# 每一个农场组都 仅 包含农场土地。且题目保证不会有两个农场组相邻，
# 也就是说一个农场组中的任何一块土地都 不会 与另一个农场组的任何一块土地在四个方向上相邻。

# land 可以用坐标系统表示，其中 land 左上角坐标为 (0, 0) ，右下角坐标为 (m-1, n-1) 。
# 请你找到所有 农场组 最左上角和最右下角的坐标。
# 一个左上角坐标为 (r1, c1) 且右下角坐标为 (r2, c2) 的 农场组 用长度为 4 的数组 [r1, c1, r2, c2] 表示。

# 请你返回一个二维数组，它包含若干个长度为 4 的子数组，每个子数组表示 land 中的一个 农场组 。
# 如果没有任何农场组，请你返回一个空数组。可以以 任意顺序 返回所有农场组。

# 要解決這個問題，我們需要找到每一塊農田的矩形區域（這些區域內的每個值都是1），並返回這些矩形的左上角和右下角的坐標。

# 解題思路
# 遍歷整個矩陣：我們需要遍歷矩陣中的每一個元素，如果該元素的值為1且未被訪問過，那麼這個位置就是一塊新的農田的左上角。我們需要找到這塊農田的右下角坐標。

# 擴展矩形區域：一旦找到一塊農田的左上角坐標，我們通過向右和向下擴展，找到矩形區域的右下角。

# 標記訪問過的區域：在擴展矩形區域的過程中，將所有訪問過的位置標記為已訪問，以防止重複計算。

# 保存結果：每找到一塊農田的矩形區域，將其左上角和右下角坐標保存到結果列表中。

# 左上角坐标为 (r1, c1) 且右下角坐标为 (r2, c2) 的 农场组 用长度为 4 的数组 [r1, c1, r2, c2] 表示。

from collections import deque
class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        if not land:
            return []

        rows, cols = len(land), len(land[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        result = []

        def bfs(row, col):
            dq = deque([(row, col)])
            r2, c2 = row, col  # 初始化右下角的坐標為當前的坐標

            while dq:
                cur_row, cur_col = dq.popleft()
                # r2, c2 = max(r2, cur_row), max(c2, cur_col)
                r2, c2 = cur_row, cur_col

                for dx, dy in directions:
                    new_r, new_c = cur_row + dx, cur_col + dy

                    if 0 <= new_r < rows and 0 <= new_c < cols and land[new_r][new_c] == 1:
                        land[new_r][new_c] = 0        # 標記為已訪問
                        dq.append((new_r, new_c))                        

            return [row, col, r2, c2]

        for row in range(rows):
            for col in range(cols):
                if land[row][col] == 1:            # 找到一個新的島嶼
                    land[row][col] = 0          # 標記為已訪問
                    result.append(bfs(row, col))         
                      
        return result

        
870