Medium

题目描述

给你一个 m x n 的二进制矩阵 land，其中 0 表示一公顷的森林，1 表示一公顷的农田。

为了让土地有组织，指定了由农田组成的矩形区域。这些矩形区域称为组。没有两个组是相邻的，这意味着一个组中的农田不会与另一个组中的农田在四个方向上相邻。

land 可以用坐标系表示，其中 land 的左上角是 (0, 0)，右下角是 (m-1, n-1)。找到每组农田的左上角和右下角的坐标。左上角在 (r1, c1) 和右下角在 (r2, c2) 的农田组用长度为 4 的数组 [r1, c1, r2, c2] 表示。

返回一个二维数组，包含 land 中每组农田的上述 4 长度数组。如果没有农田组，返回一个空数组。你可以按任何顺序返回答案。

示例 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
  • 农田组都是矩形的

解题思路

这道题的关键在于理解题意：农田组是矩形的，且不同组之间不相邻。我们需要找到每个农田组的左上角和右下角坐标。

解题思路

有两种主要解法：

方法一：DFS遍历（推荐）

  1. 遍历矩阵，当遇到值为1且未访问过的位置时，说明找到了一个新的农田组
  2. 使用DFS从该位置开始遍历整个农田组，记录遍历过程中的最小和最大坐标
  3. 将访问过的农田标记为已访问（设为0），避免重复计算
  4. 将左上角和右下角坐标加入结果

方法二：利用矩形性质优化

由于农田组都是矩形的，当我们找到一个农田组的左上角时，可以直接计算出右下角：

  1. 遍历矩阵找到每个农田组的左上角（当前位置为1，且左边和上面都不是1）
  2. 从左上角开始向右向下扩展，找到矩形的边界
  3. 将整个矩形区域标记为已访问

方法二更加高效，因为它避免了不必要的递归调用，直接利用矩形的性质来确定边界。

代码实现

class Solution {
public:
    vector<vector<int>> findFarmland(vector<vector<int>>& land) {
        vector<vector<int>> result;
        int m = land.size(), n = land[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (land[i][j] == 1) {
                    // 找到农田组的左上角
                    int r1 = i, c1 = j;
                    int r2 = i, c2 = j;
                    
                    // 找到右下角
                    while (r2 + 1 < m && land[r2 + 1][j] == 1) r2++;
                    while (c2 + 1 < n && land[i][c2 + 1] == 1) c2++;
                    
                    // 将整个矩形区域标记为0
                    for (int r = r1; r <= r2; r++) {
                        for (int c = c1; c <= c2; c++) {
                            land[r][c] = 0;
                        }
                    }
                    
                    result.push_back({r1, c1, r2, c2});
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        result = []
        m, n = len(land), len(land[0])
        
        for i in range(m):
            for j in range(n):
                if land[i][j] == 1:
                    # 找到农田组的左上角
                    r1, c1 = i, j
                    r2, c2 = i, j
                    
                    # 找到右下角
                    while r2 + 1 < m and land[r2 + 1][j] == 1:
                        r2 += 1
                    while c2 + 1 < n and land[i][c2 + 1] == 1:
                        c2 += 1
                    
                    # 将整个矩形区域标记为0
                    for r in range(r1, r2 + 1):
                        for c in range(c1, c2 + 1):
                            land[r][c] = 0
                    
                    result.append([r1, c1, r2, c2])
        
        return result

public class Solution {
    public int[][] FindFarmland(int[][] land) {
        var result = new List<int[]>();
        int m = land.Length, n = land[0].Length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (land[i][j] == 1) {
                    // 找到农田组的左上角
                    int r1 = i, c1 = j;
                    int r2 = i, c2 = j;
                    
                    // 找到右下角
                    while (r2 + 1 < m && land[r2 + 1][j] == 1) r2++;
                    while (c2 + 1 < n && land[i][c2 + 1] == 1) c2++;
                    
                    // 将整个矩形区域标记为0
                    for (int r = r1; r <= r2; r++) {
                        for (int c = c1; c <= c2; c++) {
                            land[r][c] = 0;
                        }
                    }
                    
                    result.Add(new int[]{r1, c1, r2, c2});
                }
            }
        }
        
        return result.ToArray();
    }
}

var findFarmland = function(land) {
    const m = land.length;
    const n = land[0].length;
    const result = [];
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (land[i][j] === 1) {
                let r2 = i, c2 = j;
                
                while (r2 + 1 < m && land[r2 + 1][j] === 1) {
                    r2++;
                }
                
                while (c2 + 1 < n && land[i][c2 + 1] === 1) {
                    c2++;
                }
                
                for (let r = i; r <= r2; r++) {
                    for (let c = j; c <= c2; c++) {
                        land[r][c] = 0;
                    }
                }
                
                result.push([i, j, r2, c2]);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(m×n)
空间复杂度O(1)

时间复杂度：每个位置最多被访问两次（一次在外层循环，一次在标记为0时），所以总时间复杂度为O(m×n)。

空间复杂度：除了存储结果的数组外，只使用了常数额外空间，所以空间复杂度为O(1)。

相关题目