[C++知识库]leetcode 找到所有的农场组（C++、java、python）

给你一个下标从?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.length
• n == land[i].length
• 1 <= m, n <= 300
• land?只包含?0?和?1?。
• 农场组都是?矩形?的形状。

C++

class Solution {
public:
    void dfs(vector<vector<int>>& res, vector<int>& tmp, vector<vector<int>>& land, vector<vector<int>>& flag, int r, int c) {
        if(1==land[r][c] && 0==flag[r][c]) {
            flag[r][c]=1;
            tmp[2]=max(tmp[2],r);
            tmp[3]=max(tmp[3],c);
            int dy[]={1,-1,0,0};
            int dx[]={0,0,1,-1};
            for(int k=0;k<4;k++) {
                int y=r+dy[k];
                int x=c+dx[k];
                if(y>=0 && y<land.size() && x>=0 && x<land[0].size() && 1==land[y][x]) {
                    dfs(res,tmp,land,flag,y,x);
                }
            }
        }
    }
    
    vector<vector<int>> findFarmland(vector<vector<int>>& land) {
        vector<vector<int>> res;
        int m=land.size();
        int n=land[0].size();
        vector<vector<int>> flag(m,vector<int>(n,0));
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(1==land[i][j] && 0==flag[i][j]) {
                    vector<int> tmp={i,j,i,j};
                    dfs(res,tmp,land,flag,i,j);
                    res.push_back(tmp);
                }
            }
        }
        return res;
    }
};

java

class Solution {
    private ArrayList<int[]> res = new ArrayList<>();

    public void dfs(int[][] land, int[][] flag, int[] tmp, int r, int c) {
        if (land[r][c] == 1 && flag[r][c] == 0) {
            flag[r][c] = 1;
            tmp[2] = Math.max(tmp[2], r);
            tmp[3] = Math.max(tmp[3], c);
            int[] dy = {1, -1, 0, 0};
            int[] dx = {0, 0, 1, -1};
            for (int k = 0; k < 4; k++) {
                int y = r + dy[k];
                int x = c + dx[k];
                if (y >= 0 && y < land.length && x >= 0 && x < land[0].length) {
                    dfs(land, flag, tmp, y, x);
                }
            }
        }
    }

    public int[][] findFarmland(int[][] land) {
        int m = land.length;
        int n = land[0].length;
        int[][] flag = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (land[i][j] == 1 && flag[i][j] == 0) {
                    int[] tmp = {i, j, i, j};
                    dfs(land, flag, tmp, i, j);
                    res.add(tmp);
                }
            }
        }
        int[][] ans = new int[res.size()][4];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }
}

python

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        m = len(land)
        n = len(land[0])
        flag = [[0 for j in range(n)] for i in range(m)]
        res = []
        dy = [1, -1, 0, 0]
        dx = [0, 0, 1, -1]

        def dfs(tmp, r, c):
            if 1 == land[r][c] and 0 == flag[r][c]:
                flag[r][c] = 1
                tmp[2] = max(tmp[2], r)
                tmp[3] = max(tmp[3], c)
                for k in range(4):
                    y = dy[k] + r
                    x = dx[k] + c
                    if y >= 0 and y < m and x >= 0 and x < n:
                        dfs(tmp, y, x)

        for i in range(m):
            for j in range(n):
                if 1 == land[i][j] and 0 == flag[i][j]:
                    tmp = [i, j, i, j]
                    dfs(tmp, i, j)
                    res.append(tmp)
        return res