找到所有的农场组 图解题解

农场都是矩形，要框出每组的对角

给一个 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]。

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 ans

C++

#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]);
    }
}