找到所有的农场组

1992. 找到所有的农场组

给你一个下标从 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 。
农场组都是矩形的形状。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<vector<int>> findFarmland(vector<vector<int>>& land) { } };

python3 解法, 执行用时: 152 ms, 内存消耗: 27.1 MB, 提交时间: 2022-12-05 15:43:43

class Solution:
    def findFarmland(self, land: "List[List[int]]") -> "List[List[int]]":
        m, n, res = len(land), len(land[0]), []
        for i in range(m):
            for j in range(n):
                if land[i][j] == 1:
                    r, c = i, j
                    ## 题目确保农场相互独立
                    while c < n - 1 and land[i][c + 1] == 1:
                        c += 1
                    while r < m - 1 and land[r + 1][j] == 1:
                        r += 1
                    res.append([i, j, r, c])

                    ## 退耕还林
                    for n1 in range(i, r + 1):
                        for n2 in range(j, c + 1):
                            land[n1][n2] = 0
                    
        return res

python3 解法, 执行用时: 120 ms, 内存消耗: 27.1 MB, 提交时间: 2022-12-05 15:42:58

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

golang 解法, 执行用时: 124 ms, 内存消耗: 13.2 MB, 提交时间: 2022-12-05 15:38:33

/**
判断是否为矩形左上角，需要满足三个条件：

元素值为 11；
左边是边界或者是 00；
上边是边界或者是 00。
然后遍历找到矩形的右边界和下边界。
 */
func findFarmland(a [][]int) (ans [][]int) {
	n, m := len(a), len(a[0])
	for i, row := range a {
		for j, v := range row {
			if v == 0 || j > 0 && row[j-1] == 1 || i > 0 && a[i-1][j] == 1 {
				continue
			}
			ii := i
			for ; ii+1 < n && a[ii+1][j] == 1; ii++ {}
			jj := j
			for ; jj+1 < m && a[ii][jj+1] == 1; jj++ {}
			ans = append(ans, []int{i, j, ii, jj})
		}
	}
	return
}

上一题

下一题

详情