找到所有的农场组

难度: Medium

给你一个下标从 0 开始，大小为 m x n 的二进制矩阵 land ，其中 0 表示一单位的森林土地，1 表示一单位的农场土地。

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

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

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

示例 1：

输入：land = [[1,0,0],[0,1,1],[0,1,1]]
输出：[[0,0,0,0],[1,1,2,2]]
解释：
第一个农场组的左上角为 land[0][0] ，右下角为 land[0][0] 。
第二个农场组的左上角为 land[1][1] ，右下角为 land[2][2] 。

示例 2：

输入：land = [[1,1],[1,1]]
输出：[[0,0,1,1]]
解释：
第一个农场组左上角为 land[0][0] ，右下角为 land[1][1] 。

示例 3：

输入：land = [[0]]
输出：[]
解释：
没有任何农场组。

提示：

m == land.length
n == land[i].length
1 <= m, n <= 300
land 只包含 0 和 1 。
农场组都是矩形的形状。

Submission

运行时间: 90 ms

内存: 29.1 MB

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        m, n = len(land), len(land[0])
        ans = []
        for i in range(m):
            for j in range(n):
                if (
                    land[i][j] == 0
                    or (j > 0 and land[i][j - 1] == 1)
                    or (i > 0 and land[i - 1][j] == 1)
                ):
                    continue
                x, y = i, j
                while x + 1 < m and land[x + 1][j] == 1:
                    x += 1
                while y + 1 < n and land[x][y + 1] == 1:
                    y += 1
                ans.append([i, j, x, y])
        return ans

Explain

The solution involves scanning each cell of the matrix. If a cell is the top-left corner of a new farmland group (i.e., it is '1' and neither the left neighbor nor the top neighbor is '1'), the algorithm then explores downwards and rightwards to determine the extent of this farmland group. The exploration continues until it finds a row or a column that does not consist entirely of '1's, marking the boundaries of the rectangle. These boundaries (top-left and bottom-right corners) are stored in the result list. If a cell is not the beginning of a new farmland group or is a forest land ('0'), the algorithm simply continues to the next cell.

时间复杂度: O(m*n)

空间复杂度: O(1) additional space

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        m, n = len(land), len(land[0])
        ans = []
        for i in range(m):
            for j in range(n):
                # Skip if it's forest or not a new rectangle's top-left
                if (
                    land[i][j] == 0
                    or (j > 0 and land[i][j - 1] == 1)
                    or (i > 0 and land[i - 1][j] == 1)
                ):
                    continue
                # Initialize the corners of the rectangle
                x, y = i, j
                # Find the bottom boundary of the rectangle
                while x + 1 < m and land[x + 1][j] == 1:
                    x += 1
                # Find the right boundary of the rectangle
                while y + 1 < n and land[x][y + 1] == 1:
                    y += 1
                # Append the found rectangle's corners to the result list
                ans.append([i, j, x, y])
        return ans

Explore

当判断一个单元格是否是新农场组的左上角时，检查左边和上边的单元格足以确定这一点。如果左边和上边的单元格都不是'1'，则说明当前单元格既不是已有农场组的一部分，也不是扩展中的农场组的边缘，从而是一个新农场组的开始。检查右边和下边的单元格不是必要的，因为这是在向右和向下扩展农场组时会考虑的方向，与确定一个新的左上角无关。

在确定农场组的右边界和下边界时，算法只需要沿着列向下和沿着行向右扫描来扩展当前农场组的边界。这是因为，从左上角开始，向下和向右扩展可以覆盖整个矩形区域的农场组。不需要检查每个单元格的四周，因为农场组按照题目的定义形成了矩形区块，所以只要沿着两个方向扩展即可完全确定其边界。

如果输入矩阵的大小为0，即m或n为0，该算法会在初始循环条件下立即结束循环，因为不存在任何行或列来进行迭代。因此，算法不会执行任何农场组的搜索和标记，直接返回空数组，这是正确的处理方式。

算法通过检查每个单元格左边和上边是否为'1'来确定该单元格是否可以作为新农场组的左上角。如果一个单元格的左边或上边已经是'1'，这意味着该单元格已经属于一个正在统计的农场组，因此会跳过此单元格，不将其视为新的农场组的起点。这样确保每个农场组只被计算一次，并且只有完整的未被标记的新农场组才会被识别和记录。