找到所有的农场组 图解题解
这道题到底在问什么
- 输入
- land=[[1,0,1,1,0],[0,0,0,0,0],[1,1,0,1,0],[1,1,0,1,0]]
- 输出
- [[0,0,0,0],[0,2,0,3],[2,0,3,1],[2,3,3,3]]
- 输入
- land=[[0]]
- 输出
- []
最优解：一步一步想明白
- 3记牢这一句:左上角的判据是左边和上边都不是农场。因为每个矩形组只有它真正的左上角这一格能同时满足这两条,所以每个组只会被触发一次,不重也不漏。定位到左上角后,先下探再右探,矩形的对角就出来了。下面从第 0 行第 0 列开始扫。
- 4目标:框出每个农场组先把整张图看清楚。蓝色格子是森林 0,中性色格子是农场 1。眼睛能看出四块农场:左上单格、第 0 行的横条、左下的方块、右下的竖条。但代码不会一眼看全局,它是一格一格从左到右、从上到下扫过去的,靠判左上角来发现每一个组。已记录的农场组数现在是 0。
- 5发现组 A 起点外层从 (0,0) 开始扫,这是农场。它在第 0 行第 0 列,左边和上边都出了边界、都不是农场,两条都满足,所以它就是一个农场组的左上角。抓住它,开始向下、向右扩,把这个组的矩形框出来。
- 6下探到底 r2=0先沿着第 0 列往下探。看下一行 (1,0) 是森林 0,下不去了,所以这个组的最下行就停在第 0 行,r2 等于 0。这一列只有它自己一格高。
- 7组 A 已框定,组数=1再从最下行往右探。右边 (0,1) 是森林 0,右不动了,最右列也停在第 0 列。左上角 (0,0),右下角 (0,0),这是个单格组,记下 [0,0,0,0],整块涂绿。农场组数变成 1。
- 8森林格,略过继续往右扫到 (0,1),它是森林 0,不是农场,直接跳过。扫描只在农场格上才可能触发判定。
- 9发现组 B 起点扫到 (0,2),这是农场。它左边 (0,1) 是森林,上边出了边界,左、上都不是农场,判定成立,它是一个新组的左上角。开始下探、右探。
- 10下探到底 r2=0沿第 2 列往下,下一行 (1,2) 是森林 0,下不去,最下行停在第 0 行,r2 等于 0。这个组也只有一行高。
- 11右探中 c2=3从第 0 行往右探,右边 (0,3) 还是农场,能扩,最右列推进到第 3 列,c2 先记成 3。再看它右边还有没有农场。
- 12组 B 已框定,组数=2再往右 (0,4) 是森林 0,右探到头,最右列定在第 3 列。左上角 (0,2),右下角 (0,3),这是个横着的两格组,记下 [0,2,0,3],整条涂绿。农场组数到 2。
- 13同组内部,略过扫描继续走到 (0,3)。它虽然是农场,但左边 (0,2) 也是农场,说明它不是最左那格,已经属于刚才框好的组 B。判据里左邻是农场就跳过,不会重新开一个组。这正是不重复的关键。
- 14空行,略过第 0 行扫完,进到第 1 行。这一行 (1,0) 到 (1,4) 全是森林 0,一个农场都没有,整行都不会触发判定,快速略过。农场组之间隔着的,正是这样的森林带。
- 15发现组 C 起点进到第 2 行,扫到 (2,0),它是农场。它在第 0 列没有左邻,上边 (1,0) 是森林,左、上都不是农场,判定成立,又一个新组的左上角。这次的组要大一些,认真下探。
- 16下探中 r2=3沿第 0 列往下,下一行 (3,0) 还是农场,能下去,最下行推进到第 3 行,r2 记成 3。继续看还能不能再往下。
- 17下探到底 r2=3再往下就是第 4 行,已经出了矩阵的下边界,下探到此为止,最下行定在第 3 行。注意接下来的右探要从这一最下行、也就是第 3 行出发,而不是从起点那行。
- 18右探中 c2=1从最下行第 3 行往右探。右边 (3,1) 是农场,能扩,最右列推到第 1 列,c2 记成 1。因为组是矩形,底行的宽度就是整个组的宽度,所以从底行量最省事。
- 19组 C 已框定,组数=3再往右 (3,2) 是森林 0,右探到头,最右列定在第 1 列。左上角 (2,0),右下角 (3,1),这是个 2 乘 2 的方块,记下 [2,0,3,1],整块涂绿。农场组数到 3。你看,虽然只走了一列加一行,整个矩形的四角就都定出来了。
- 20同组内部,略过扫描回到第 2 行接着走,来到 (2,1)。它是农场,但左边 (2,0) 也是农场,它属于刚框好的组 C,不是左上角,跳过。组 C 的其余格子都会这样被判为同组内部而略过。
- 21发现组 D 起点第 2 行继续,扫到 (2,3),农场。它左边 (2,2) 是森林,上边 (1,3) 也是森林,左、上都不是农场,最后一个新组的左上角就是它。
- 22下探到底 r2=3沿第 3 列往下,下一行 (3,3) 还是农场,下去,最下行到第 3 行,r2 等于 3。再往下出界,下探停在这里。
- 23组 D 已框定,组数=4从第 3 行往右探,右边 (3,4) 是森林 0,右不动,最右列停在第 3 列。左上角 (2,3),右下角 (3,3),这是个竖着的两格组,记下 [2,3,3,3],涂绿。农场组数到 4,四个组都框好了。
- 24同组内部,略过扫到第 3 行的 (3,0)。它是农场,左边没有邻居,但上边 (2,0) 是农场,说明它不是最上那格,属于组 C。上邻是农场就跳过。判据把左和上都管住,才能保证只有真正的左上角这一格会触发。
- 25同组内部,略过再看 (3,3),它是农场,上边 (2,3) 也是农场,属于刚框好的组 D,同样跳过。剩下的格子要么是森林、要么是同组内部,都不会再开新组。
- 26答案 = 4 组整张图扫完了。四个绿色矩形就是四个农场组:单格 [0,0,0,0]、横条 [0,2,0,3]、方块 [2,0,3,1]、竖条 [2,3,3,3]。全程没有用递归、没有开访问数组,只靠判左上角加两次直线扩边界,就把每个矩形的对角坐标都拿到了。这就是最终答案,共 4 组。
⚠️ 容易写错的地方
✗ 错：把左上角的判据写成「只要左邻不是农场」
✓ 对：必须左邻和上邻都不是农场
只看左邻,一个竖条组里除了顶格,每一格左边都没农场、会被误判成新的左上角,同一个组被重复记录
✗ 错：扩右时从起始行 i 去量宽度
✓ 对：要从下探得到的最下行 x 出发向右扩
参考代码读的是 land[x][y+1];矩形每行宽度虽相同,但代码固定用最下行 x,照抄这个写法最稳,别把 x 写回成 i
✗ 错：用洪水填充 DFS 递归求每块的行列极值
✓ 对：本解直接判角标加两次直线扩边界
DFS 也能算对,但要么开访问数组要么吃递归栈,空间 O(m 乘 n);利用矩形加不相邻的性质,本解空间能做到 O(1)
✗ 错：忘了本格是森林 0 也要在跳过条件里
✓ 对：跳过条件第一条就是 land[i][j] 等于 0
森林格不属于任何组,若不先排除,后面的下探右探会从一片森林里胡乱扩，得到错误矩形
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> findFarmland(vector<vector<int>>& land) {
vector<vector<int>> ans;
int m = land.size();
int n = land[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (land[i][j] == 0 || (j > 0 && land[i][j - 1] == 1) || (i > 0 && land[i - 1][j] == 1)) continue;
int x = i;
int y = j;
for (; x + 1 < m && land[x + 1][j] == 1; ++x)
;
for (; y + 1 < n && land[x][y + 1] == 1; ++y)
;
ans.push_back({i, j, x, y});
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int[][] findFarmland(int[][] land) {
List<int[]> ans = new ArrayList<>();
int m = land.length;
int n = land[0].length;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (land[i][j] == 0 || (j > 0 && land[i][j - 1] == 1)
|| (i > 0 && land[i - 1][j] == 1)) {
continue;
}
int x = i;
int y = j;
for (; x + 1 < m && land[x + 1][j] == 1; ++x)
;
for (; y + 1 < n && land[x][y + 1] == 1; ++y)
;
ans.add(new int[] {i, j, x, y});
}
}
return ans.toArray(new int[ans.size()][4]);
}
}复杂度
时间
O(m·n)
m 行 n 列共 m 乘 n 个格子。外层把每个格子扫一遍;向下、向右扩边界时,每个农场格总共只会被某个组的扩展经过常数次,所有扩展加起来不超过农场格总数。合计随格子总数线性增长
空间
O(1)
按峰值算,不计返回的答案数组。没有递归栈、没有额外访问表,只用了 i,j,x,y 几个下标变量。这正是它比洪水填充省的地方:洪水填充要么开访问数组、要么吃递归栈,都是 O(m·n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 找到所有的农场组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心思路是什么?+
利用农场组都是矩形、彼此不相邻这两个性质。逐格扫描,一个农场格如果左邻和上邻都不是农场,它就是某个组的左上角;每个组只有这一格满足,所以不重不漏。抓到左上角后先向下扩得到最下行,再从最下行向右扩得到最右列,记下 [左上行,左上列,最下行,最右列] 即可。
不利用矩形性质,还能怎么做?+
可以退回到通用的洪水填充:在每块相连的农场上做 DFS 或 BFS,过程中维护经过格子的最小行、最小列、最大行、最大列,走完这块就得到它的外接矩形。也可以用并查集把相邻农场合并,再按根节点归拢每块的行列极值。这些做法对不规则形状也成立,但空间是 O(m 乘 n)。
为什么这个解法空间能做到 O(1)?+
因为它不递归、不开访问数组。判左上角只看当前格的左邻和上邻,扩边界只用几个下标变量在原矩阵上走直线,不修改矩阵也不额外记录访问状态。所以除了必须返回的答案数组,额外空间是常数;而洪水填充要么吃递归栈、要么开访问表,都是 O(m 乘 n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 找到所有的农场组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。