网站快照不更新原因,网站安全,免费空间申请哪个好,专业建设网站技术文章目录1. 题目2. 解题1. 题目
给你一个下标从 0 开始#xff0c;大小为 m x n 的二进制矩阵 land #xff0c;其中 0 表示一单位的森林土地#xff0c;1 表示一单位的农场土地。
为了让农场保持有序#xff0c;农场土地之间以矩形的 农场组 的形式存在。 每一个农场组都…
文章目录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:vectorvectorint findFarmland(vectorvectorint land) {int m land.size(), n land[0].size(), k 300;queueint q;vectorvectorint ans;vectorvectorint 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){vectorint pos {i,j,i,j};q.push(i*kj);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(nx0 nx m ny0 nyn land[nx][ny]){land[nx][ny] 0;q.push(nx*kny);}}}ans.push_back(pos);}}}return ans;}
};156 ms 60.9 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
