Leetcode 1992. 找到所有的农场组(可以,一次过)
2022/6/11 23:50:35
本文主要是介绍Leetcode 1992. 找到所有的农场组(可以,一次过),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给你一个下标从 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 。
- 农场组都是 矩形 的形状。
Code:
class Solution { public: vector<vector<int>> findFarmland(vector<vector<int>>& land) { vector<vector<int>>res; vector<vector<int>>pos(land.size(),vector<int>(land[0].size(),0)); for(int i=0;i<land.size();i++) { vector<int>sub=land[i]; for(int j=0;j<sub.size();j++) { if(pos[i][j]==1) continue; if(sub[j]!=1) continue; int startx=-1; int starty=-1; int endx=-1; int endy=-1; bool is=false; if(sub[j]==1) { is=true; pos[i][j]=1; startx=i; starty=j; endx=i; endy=j; bool flag=false; for(int k=i;k<land.size();k++) { if(land[k][j]!=1) { endx=k-1; flag=true; break; } else { // pos[k][j]=1; } } if(!flag) { // pos[land.size()-1][j]=1; endx=land.size()-1; } flag=false; for(int k=j;k<sub.size();k++) { if(land[i][k]!=1) { endy=k-1; flag=true; break; } else { // pos[i][k]=1; } } if(!flag) { // pos[i][sub.size()-1]=1; endy=sub.size()-1; } for(int ii=startx;ii<=endx;ii++) { for(int jj=starty;jj<=endy;jj++) { pos[ii][jj]=1; } } } if(is) { vector<int>vec; vec.push_back(startx); vec.push_back(starty); vec.push_back(endx); vec.push_back(endy); res.push_back(vec); } } } return res; } };
这篇关于Leetcode 1992. 找到所有的农场组(可以,一次过)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升