LeetCode 1992. 找到所有的农场组（BFS）

Michael阿明

发布于 2022-01-07 11:23:16

18000

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

文章目录
1. 题目
2. 解题

1. 题目

给你一个下标从 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 。
农场组都是 矩形 的形状。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-all-groups-of-farmland 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

BFS，广度优先搜索，DFS也可以

class Solution {
public:
    vector<vector<int>> findFarmland(vector<vector<int>>& land) {
        int m = land.size(), n = land[0].size(), k = 300;
        queue<int> q;
        vector<vector<int>> ans;
        vector<vector<int>> dir = {{0,1},{1,0},{-1,0},{0,-1}};
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(land[i][j] == 1)
                {
                    vector<int> pos = {i,j,i,j};
                    q.push(i*k+j);
                    land[i][j] = 0; // 访问过了
                    while(!q.empty())
                    {
                        int num = q.front();
                        int x = num/k;
                        int y = num%k;
                        q.pop();
                        pos[0] = min(pos[0], x);
                        pos[1] = min(pos[1], y);
                        pos[2] = max(pos[2], x);
                        pos[3] = max(pos[3], y);
                        for(int d = 0; d < 4; ++d)
                        {
                            int nx = x + dir[d][0];
                            int ny = y + dir[d][1];
                            if(nx>=0 && nx < m && ny>=0 && ny<n && land[nx][ny])
                            {
                                land[nx][ny] = 0;
                                q.push(nx*k+ny);
                            }
                        }
                    }
                    ans.push_back(pos);
                }
            }
        }
        return ans;
    }
};

156 ms 60.9 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/09/05 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https