LeetCode 题解工作台
找到所有的农场组
给你一个下标从 0 开始，大小为 m x n 的二进制矩阵 land ，其中 0 表示一单位的森林土地， 1 表示一单位的农场土地。 为了让农场保持有序，农场土地之间以矩形的 农场组 的形式存在。每一个农场组都 仅 包含农场土地。且题目保证不会有两个农场组相邻，也就是说一个农场组中的任何一块土地都 …
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
class Solution: def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个下标从 0 开始，大小为 m x n 的二进制矩阵 land ，其中 0 表示一单位的森林土地，1 表示一单位的农场土地。
为了让农场保持有序，农场土地之间以矩形的 农场组 的形式存在。每一个农场组都 仅 包含农场土地。且题目保证不会有两个农场组相邻，也就是说一个农场组中的任何一块土地都 不会 与另一个农场组的任何一块土地在四个方向上相邻。
land 可以用坐标系统表示，其中 land 左上角坐标为 (0, 0) ，右下角坐标为 (m-1, n-1) 。请你找到所有 农场组 最左上角和最右下角的坐标。一个左上角坐标为 (r1, c1) 且右下角坐标为 (r2, c2) 的 农场组 用长度为 4 的数组 [r1, c1, r2, c2] 表示。
请你返回一个二维数组，它包含若干个长度为 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.lengthn == land[i].length1 <= m, n <= 300land只包含0和1。- 农场组都是 矩形 的形状。
解题思路
方法一
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(M * N) since each cell is visited once during scanning and DFS. Space complexity is O(1) if we mark visited cells in-place or O(M * N) if using extra visited storage. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
They may ask how to detect top-left corners efficiently.
- question_mark
Expect discussion of DFS versus BFS for rectangle expansion.
- question_mark
They could probe edge cases like single-cell or full-matrix farmland.
常见陷阱
外企场景- error
Failing to check for non-adjacent groups can merge separate rectangles.
- error
Using BFS without careful boundary checks may miss edges of rectangles.
- error
Incorrectly updating coordinates can lead to off-by-one errors in output.
进阶变体
外企场景- arrow_right_alt
Return the area of each farmland group instead of coordinates.
- arrow_right_alt
Find groups when farmland can be irregular instead of rectangular.
- arrow_right_alt
Use BFS exclusively to expand rectangles rather than DFS.