题目描述
给你一个下标从 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 中的一个 农场组 。如果没有任何农场组，请你返回一个空数组。可以以 任意顺序 返回所有农场组。
Example 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] 。
Example 2:
输入：land = [[1,1],[1,1]] 输出：[[0,0,1,1]] 解释： 第一个农场组左上角为 land[0][0] ，右下角为 land[1][1] 。
Example 3:
输入：land = [[0]] 输出：[] 解释： 没有任何农场组。
Constraints:
- m == land.length
- n == land[i].length
- 1 <= m, n <= 300
- land 只包含 0 和 1 。
- 农场组都是 矩形 的形状。
解题思路
- dfs模版的变形
C++代码
class Solution {
public:
void dfs(vector<vector<int>>& land, int x, int y, int& a, int& b){
int row = land.size();
int col = land[0].size();
if(x >= row || x < 0 || y >= col || y < 0 || land[x][y] == 0){
return;
}
land[x][y] = 0;
if((x + 1 == row || land[x + 1][y] == 0) &&
(y + 1 == col || land[x][y + 1] == 0)){
if(x > a){ // 这里是为了更新a，b
a = x;
}
if(y > b){
b = y;
}
return;
}
dfs(land, x + 1, y, a, b);
dfs(land, x, y + 1, a, b);
}
vector<vector<int>> findFarmland(vector<vector<int>>& land) {
vector<vector<int>> res;
for(int i = 0; i < land.size(); i++){
for(int j = 0; j < land[0].size(); j++){
if(land[i][j] == 0){
continue;
}
int a = i, b = j;
dfs(land, i, j, a, b);
res.push_back({i, j, a, b});
}
}
return res;
}
};
