题目描述
思路解析
一句话答案：LeetCode 1992 找到所有的农场组：农场组都是彼此不相邻的矩形，逐格扫描只从左邻、上邻都不是农场的左上角起，向下再向右扩出对角，省掉洪水填充，时间 O(m·n)、空间 O(1)。
农场都是矩形，要框出每组的对角
给一个 m 行 n 列、只含 0 和 1 的矩阵 land,0 是森林、1 是农场，相连的一片农场算一个农场组。题目保证：每组都是实心矩形，组间隔着森林、绝不相邻。要返回每组左上角与右下角坐标 [r1,c1,r2,c2]。题面这张 land=[[1,0,1,1,0],[0,0,0,0,0],[1,1,0,1,0],[1,1,0,1,0]] 有四块农场。
洪水填充能算对，可空间省不下来
通用做法是洪水填充，从一个农场格出发把连成一片的农场全走一遍，记下经过格子的最小行、最小列、最大行、最大列，四个极值就是外接矩形。它对任何形状都成立，却要么开一个和矩阵一样大的访问数组防重复，要么靠递归压栈，空间都是 O(m·n)。可这题保证每组是矩形、组间不相邻，这两条性质洪水填充都没用上。
只盯左上角，照样不重也不漏
既然每组都是矩形，一整块的信息只压在左上角这一格上。判据很干脆：一个农场格，左邻和上邻都不是农场，它就是某个组的左上角。矩形里只有那一格能同时满足两条，其余格子要么上邻、要么左邻是自家农场，都被挡下。于是每个组恰好被左上角触发一次，不漏也不重。抓到它后，先沿这列向下扩到最下行，再从最下行向右扩到最右列，对角就出来了。
扫到左上角，先向下再向右扩出对角
外层双重循环把每格扫一遍。三种情况跳过：本格森林 0、左邻是农场、上邻是农场，沾一条就不是左上角。都不沾才扩：从起点 i 往下走，下一行同列还是农场就加一，碰森林或出界就停，得到最下行 x；再从最下行往右走，右一列还是农场就加一，到头即停，得到最右列 y，记下 [i,j,x,y]。向右从最下行 x 量、别回起点行 i，矩形每行同宽，照代码固定用最下行。
拿题面这张图挨格扫过去
扫到 (0,0)：没左邻上邻，左上角；向下、向右都是森林，记单格 [0,0,0,0]。到 (0,2)：左邻森林、无上邻，又一左上角；向下森林，向右 (0,3) 农场、(0,4) 森林，记横条 [0,2,0,3]。(0,3) 左邻是农场，归这条、跳过。
第 1 行全森林略过。(2,0)：无左邻、上邻森林，左上角；向下 (3,0) 农场、再下出界得最下行第 3 行，从第 3 行右探 (3,1) 农场、(3,2) 森林，记方块 [2,0,3,1]。(2,3)：左、上皆森林，左上角；向下出界、向右森林，记竖条 [2,3,3,3]。四框正对答案。
线性时间、常数空间，几处别写岔
时间 O(m·n)：每格扫一遍，扩边界时每个农场格总共只被经过常数次。空间 O(1)：不递归、不开访问数组，只有 i、j、x、y 几个下标在原矩阵上走直线，这正是它比洪水填充省的地方。
有几处最易写岔。判据只写「左邻不是农场」，竖条组里除顶格外每格左邻都空、会被误当成新左上角、同组记好几遍，必须左邻上邻同时不是农场。向右扩把 x 写回起点行 i、遇缺角会量错宽度，认最下行 x 最稳。跳过条件还得先排除森林 0，漏了会从森林里硬扩出假矩形。全森林 land=[[0]] 触发不了左上角、返回空，单格农场触发一次得 [0,0,0,0]。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:左上角的判据是左边和上边都不是农场。因为每个矩形组只有它真正的左上角这一格能同时满足这两条,所以每个组只会被触发一次,不重也不漏。定位到左上角后,先下探再右探,矩形的对角就出来了。下面从第 0 行第 0 列开始扫。
整张 land · 四个矩形待框定：先把整张图看清楚。蓝色格子是森林 0,中性色格子是农场 1。眼睛能看出四块农场:左上单格、第 0 行的横条、左下的方块、右下的竖条。但代码不会一眼看全局,它是一格一格从左到右、从上到下扫过去的,靠判左上角来发现每一个组。已记录的农场组数现在是 0。
扫到 (0,0) · 判定左上角：外层从 (0,0) 开始扫,这是农场。它在第 0 行第 0 列,左边和上边都出了边界、都不是农场,两条都满足,所以它就是一个农场组的左上角。抓住它,开始向下、向右扩,把这个组的矩形框出来。
组 A 向下探 · 下一行是森林：先沿着第 0 列往下探。看下一行 (1,0) 是森林 0,下不去了,所以这个组的最下行就停在第 0 行,r2 等于 0。这一列只有它自己一格高。
组 A 向右探 · 右邻是森林,记录 [0,0,0,0]：再从最下行往右探。右边 (0,1) 是森林 0,右不动了,最右列也停在第 0 列。左上角 (0,0),右下角 (0,0),这是个单格组,记下 [0,0,0,0],整块涂绿。农场组数变成 1。
扫到 (0,1) · 森林,跳过：继续往右扫到 (0,1),它是森林 0,不是农场,直接跳过。扫描只在农场格上才可能触发判定。
扫到 (0,2) · 判定左上角：扫到 (0,2),这是农场。它左边 (0,1) 是森林,上边出了边界,左、上都不是农场,判定成立,它是一个新组的左上角。开始下探、右探。
组 B 向下探 · 下一行是森林：沿第 2 列往下,下一行 (1,2) 是森林 0,下不去,最下行停在第 0 行,r2 等于 0。这个组也只有一行高。
组 B 向右探 · 右邻是农场,继续：从第 0 行往右探,右边 (0,3) 还是农场,能扩,最右列推进到第 3 列,c2 先记成 3。再看它右边还有没有农场。
组 B 向右探停 · 记录 [0,2,0,3]：再往右 (0,4) 是森林 0,右探到头,最右列定在第 3 列。左上角 (0,2),右下角 (0,3),这是个横着的两格组,记下 [0,2,0,3],整条涂绿。农场组数到 2。
扫到 (0,3) · 左邻是农场,跳过：扫描继续走到 (0,3)。它虽然是农场,但左边 (0,2) 也是农场,说明它不是最左那格,已经属于刚才框好的组 B。判据里左邻是农场就跳过,不会重新开一个组。这正是不重复的关键。
扫第 1 行 · 整行都是森林：第 0 行扫完,进到第 1 行。这一行 (1,0) 到 (1,4) 全是森林 0,一个农场都没有,整行都不会触发判定,快速略过。农场组之间隔着的,正是这样的森林带。
扫到 (2,0) · 判定左上角：进到第 2 行,扫到 (2,0),它是农场。它在第 0 列没有左邻,上边 (1,0) 是森林,左、上都不是农场,判定成立,又一个新组的左上角。这次的组要大一些,认真下探。
组 C 向下探 · 下一行还是农场：沿第 0 列往下,下一行 (3,0) 还是农场,能下去,最下行推进到第 3 行,r2 记成 3。继续看还能不能再往下。
组 C 向下探停 · 触底出界：再往下就是第 4 行,已经出了矩阵的下边界,下探到此为止,最下行定在第 3 行。注意接下来的右探要从这一最下行、也就是第 3 行出发,而不是从起点那行。
组 C 向右探(第 3 行)· 右邻是农场：从最下行第 3 行往右探。右边 (3,1) 是农场,能扩,最右列推到第 1 列,c2 记成 1。因为组是矩形,底行的宽度就是整个组的宽度,所以从底行量最省事。
组 C 向右探停 · 记录 [2,0,3,1]：再往右 (3,2) 是森林 0,右探到头,最右列定在第 1 列。左上角 (2,0),右下角 (3,1),这是个 2 乘 2 的方块,记下 [2,0,3,1],整块涂绿。农场组数到 3。你看,虽然只走了一列加一行,整个矩形的四角就都定出来了。
扫到 (2,1) · 左邻是农场,跳过：扫描回到第 2 行接着走,来到 (2,1)。它是农场,但左边 (2,0) 也是农场,它属于刚框好的组 C,不是左上角,跳过。组 C 的其余格子都会这样被判为同组内部而略过。
扫到 (2,3) · 判定左上角：第 2 行继续,扫到 (2,3),农场。它左边 (2,2) 是森林,上边 (1,3) 也是森林,左、上都不是农场,最后一个新组的左上角就是它。
组 D 向下探 · 下一行还是农场：沿第 3 列往下,下一行 (3,3) 还是农场,下去,最下行到第 3 行,r2 等于 3。再往下出界,下探停在这里。
组 D 向右探停 · 记录 [2,3,3,3]：从第 3 行往右探,右边 (3,4) 是森林 0,右不动,最右列停在第 3 列。左上角 (2,3),右下角 (3,3),这是个竖着的两格组,记下 [2,3,3,3],涂绿。农场组数到 4,四个组都框好了。
扫到 (3,0) · 上邻是农场,跳过：扫到第 3 行的 (3,0)。它是农场,左边没有邻居,但上边 (2,0) 是农场,说明它不是最上那格,属于组 C。上邻是农场就跳过。判据把左和上都管住,才能保证只有真正的左上角这一格会触发。
扫到 (3,3) · 上邻是农场,跳过：再看 (3,3),它是农场,上边 (2,3) 也是农场,属于刚框好的组 D,同样跳过。剩下的格子要么是森林、要么是同组内部,都不会再开新组。
回放 · 四个农场组全部框定：整张图扫完了。四个绿色矩形就是四个农场组:单格 [0,0,0,0]、横条 [0,2,0,3]、方块 [2,0,3,1]、竖条 [2,3,3,3]。全程没有用递归、没有开访问数组,只靠判左上角加两次直线扩边界,就把每个矩形的对角坐标都拿到了。这就是最终答案,共 4 组。
边界想清:全森林返回空、单格农场记 [0,0,0,0]、整块方块只被左上角 (0,0) 触发一次得到 [0,0,1,1]。
面试重点:判左上角加两次直线扩边界、也可退回洪水填充或并查集求外接矩形、本解空间 O(1) 胜在不递归不开表。
参考代码
from __future__ import annotationsfrom 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 ans复杂度
- 时间：O(m·n)，m 行 n 列共 m 乘 n 个格子。外层把每个格子扫一遍;向下、向右扩边界时,每个农场格总共只会被某个组的扩展经过常数次,所有扩展加起来不超过农场格总数。合计随格子总数线性增长
- 空间：O(1)，按峰值算,不计返回的答案数组。没有递归栈、没有额外访问表,只用了 i,j,x,y 几个下标变量。这正是它比洪水填充省的地方:洪水填充要么开访问数组、要么吃递归栈,都是 O(m·n)
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问不利用矩形性质,还能怎么做?
追问为什么这个解法空间能做到 O(1)?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
网格游戏
LeetCode 2017 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题