【剑斩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; } };