当前位置: 首页 > article >正文

Leetcode.1992 找到所有的农场组

题目链接

Leetcode.1992 找到所有的农场组 Rating : 1539

题目描述

给你一个下标从 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 = = l a n d . l e n g t h m == land.length m==land.length
  • n = = l a n d [ i ] . l e n g t h n == land[i].length n==land[i].length
  • 1 < = m , n < = 300 1 <= m, n <= 300 1<=m,n<=300
  • land只包含 01
  • 农场组都是 矩形 的形状。

解法:dfs

我们在 dfs 遍历 农场组 (全为 1 的位置 )时,需要记录这个农场组的 左上节点 ( x 1 , y 1 ) (x1,y1) (x1,y1)右下节点 ( x 2 , y 2 ) (x2,y2) (x2,y2)

由于我们是从左上角开始遍历的,所以 左上节点 ( x 1 , y 1 ) (x1,y1) (x1,y1) 最开始就确定了。

所以我们每次只需要更新 右下节点 ( x 2 , y 2 ) (x2,y2) (x2,y2) 即可。

时间复杂度: O ( m n ) O(mn) O(mn)

C++代码;

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
class Solution {
public:
    vector<vector<int>> findFarmland(vector<vector<int>>& g) {
        int m = g.size() , n = g[0].size();

        bool st[m][n];
        memset(st,false,sizeof st);

        function<void(int,int,int&,int&)> dfs = [&](int i,int j,int& x2,int& y2) ->void{
            if(i < 0 || i >= m || j < 0 || j >= n || g[i][j] == 0 || st[i][j]) return;
            
            st[i][j] = true;

            if(i > x2 || j > y2){
                x2 = i, y2 = j;
            }

            for(int k = 0;k < 4;k++){
                dfs(i + dx[k] , j + dy[k],x2,y2);
            }
        };

        vector<vector<int>> ans;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(g[i][j] && !st[i][j]){
                    int x1 = i , y1 = j , x2 = i, y2 = j;
                    dfs(i,j,x2,y2);
                    ans.push_back({x1,y1,x2,y2});
                }
            }
        }

        return ans;
    }
};


http://www.kler.cn/news/10223.html

相关文章:

  • NumPy 秘籍中文第二版:十、Scikits 的乐趣
  • vue3+TS+Pinia+Vite项目实战之一
  • 程序员的日常瞎想,个人规划,和企业把控之间的微妙关系。职场人你懂!!
  • WPF MVVM模式构建项目
  • “三步走”推动云原生转型之路
  • Unity资源-音效初识
  • 【MySQL】表的约束
  • Wijmo JavaScript UI 5.20222.877 Crack
  • ESLint的配置
  • 使用向量机(SVM)算法的推荐系统
  • Flutter系列(七)ListView 图文列表详解
  • sourcemap文件泄露漏洞
  • C++开发必知的内存问题及常用的解决方法-经典文章
  • 算法自学__ 莫队
  • 比较系统的学习 pandas (2)
  • 18从零开始学Java之switch分支语句中该怎么用?
  • 【工作感悟】老程序员总结的四条工作经验教训
  • 表格软件界的卷王,Excel、access、foxpro全靠边,WPS:真荣幸
  • 3.1.2栈的顺序存储实现
  • 十分钟教你部署一个属于自己的chatgpt网站
  • WebSpider蓝蜘蛛网页抓取工具5.1用户手册
  • 10.网络爬虫—MongoDB详讲与实战
  • 多元函数的基本概念——“高等数学”
  • 编译原理期末速成笔记
  • 最详细的Ubuntu服务器搭建Stable-Diffusion教程(无显卡,仅用CPU)
  • 【CV】Latent diffusion model 扩散模型体验
  • Eyeshot Ultimate 2023 Crack
  • k8s部署sonarqube
  • C++11 如何区分右值引用与万能引用
  • QtSqlite加密--QtCipherSqlitePlugin的使用