【剑斩OFFER】算法的暴力美学——力扣 1020 题：飞地的数量

一、题目描述

二、算法原理

思路：使用 BFS 算法先处理边界 1 ，再使用 BFS 统计陆地，体现正难则反的思想；

例如：

1）创建一个二维数组来专门标记是否入过队列或者说遍历过；

2）使用 BFS 算法标记边界为 1 的情况；

3）此时整个只有中间被0围起来的1为陆地；

三、代码实现

class Solution {
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};
typedef pair<int,int> PII;
int n,m;
public:
int numEnclaves(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
vector<vector<bool>> vis(grid.size(),vector<bool>(grid[0].size(),false));//标记遍历过的数组

for(int i = 0; i < m; i++)//处理边界1
{
Bfs(0,i,grid,vis);
Bfs(n – 1,i,grid,vis);
}
for(int i = 0; i < n; i++)//处理边界1
{
Bfs(i,0,grid,vis);
Bfs(i,m – 1,grid,vis);
}

int ret = 0;

for(int i = 0; i < n; i++)//此时中间的 1 就是陆地
{
for(int j = 0; j < m; j++)
{
if(vis[i][j] == false && grid[i][j])
{
ret += Bfs(i,j,grid,vis);
}
}
}
return ret;
}
int Bfs(int i,int j,vector<vector<int>>& grid,vector<vector<bool>>& vis)//BFS 算法
{
if(grid[i][j] != 1 || vis[i][j] != false) return 0;

queue<PII> que;
que.push({i,j});
vis[i][j] = true;
int count = 1;
while(que.size())
{
auto [x,y] = que.front();
que.pop();
for(int v = 0; v < 4; v++)
{
int a = x + dx[v];
int b = y + dy[v];
if(a >= 0 && a < n && b >= 0 && b < m && vis[a][b] == false && grid[a][b] == 1)
{
vis[a][b] = true;
que.push({a,b});
count++;
}
}
}
return count;
}
};