1992. Find All Groups of Farmland

2024-02-27 00:08

文章标签 find groups 1992 farmland

本文主要是介绍1992. Find All Groups of Farmland，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题给出了所有的1组成的形状是四边形，让给出每个农田/陆地的左上角和右下角的坐标。

这道题目还是千篇一路的bfs来遍历每个点，最鸡贼的如何判断当前点是右下角的点。

1. 正下方和右侧的点都是森林、海洋

2. 当前点在边界。

if((newy == col -1 || land[newx][newy+1] == 0) && ((newx == row -1) || land[newx+1][newy] == 0))

这个鸡贼的地方不难理解。处理完这个就能进行其他的了。

代码如下：

class Solution {
public:
vector<int> bfs(int i, int j,vector<vector<int>>& land)
{
vector<int> ret{i,j};
queue<pair<int,int>> myqueue;
vector<int> dircX{0,-1,0,0,1};
vector<int> dircY{-1,0,0,1,0};
int row = land.size();
int col = land[0].size();


myqueue.push({i,j});

while(!myqueue.empty()){
pair<int, int> cur = myqueue.front();
myqueue.pop();
int x = cur.first;
int y = cur.second;

for(int i =0;i<5;i++) {
int newx = x + dircX[i];
int newy = y + dircY[i];

if(newx<0 || newx >= row || newy <0 || newy >= col)
continue;
else if(land[newx][newy] == 1){
myqueue.push({newx, newy});
land[newx][newy] = -1;
// 这里是关键点，如何判断当前grid是最右边的点？
// 看图知道，最右下角的点满足以下情况：
// 1. 正下方的点和右侧的点是森林 land[newx][newy+1] == 0) && land[newx+1][newy] == 0
// 2. 或者该点在边沿。newy == col -1 (newx == row -1)
if((newy == col -1 || land[newx][newy+1] == 0) && ((newx == row -1) || land[newx+1][newy] == 0)) {
ret.push_back(newx);
ret.push_back(newy);
}
}
}
}

return ret;

}

vector<vector<int>> findFarmland(vector<vector<int>>& land) {
int row = land.size();
int col = land[0].size();
vector<vector<int>> ret={};

for(int i =0;i<row;i++)
{
for(int j=0;j<col;j++)
{
if(land[i][j] == 1) {
vector<int> tmp = bfs(i, j, land);
ret.push_back(tmp);
}
}
}
return ret;
}
};