地址 https://leetcode-cn.com/contest/weekly-contest-162/problems/number-of-closed-islands/
有一个二维矩阵 grid ，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。
我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。
如果一座岛屿 完全 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。
请返回封闭岛屿的数目。
示例1
输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。
示例2
输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出：1
示例3
输入：grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
输出：2
题解 基本都是使用DFS 查找是否与边界的0有所连通
这里提供另一种思路 并查集
检测所有标记为陆地的0 进行归并 然后将与边界连通的陆地集合删除 最后留下的就是封闭岛屿
代码
1 class Solution { 2 public: 3 4 int MAX_NUM; 5 vector<vector<int>> field; 6 vector<int> fa; 7 vector<int> addx; 8 vector<int> addy; 9 void init(int n) 10 { 11 for (int i = 0; i <= n; i++) 12 fa[i] = i; 13 } 14 int get(int x) 15 { 16 return fa[x] == x ? x : fa[x] = get(fa[x]);//路径压缩,防止链式结构 17 } 18 void merge(int x, int y) 19 { 20 fa[get(x)] = get(y); 21 } 22 //================================================ 23 void check(int x, int y, vector<vector<int>>& grid) 24 { 25 for (int i = 0; i < 4; i++) { 26 int newx = x + addx[i]; 27 int newy = y + addy[i]; 28 29 if (newx >= 0 && newx < grid.size() && newy >= 0 && newy < grid[0].size() 30 && grid[newx][newy] == 0) 31 { 32 int idx = x * grid[0].size() + y; 33 int anotherIdx = newx * grid[0].size() + newy; 34 merge(idx, anotherIdx); 35 } 36 } 37 } 38 39 int closedIsland(vector<vector<int>>& grid) { 40 MAX_NUM = 110; 41 field = vector<vector<int>>(MAX_NUM, vector<int>(MAX_NUM)); 42 fa = vector<int>(MAX_NUM*MAX_NUM + 1); 43 init(MAX_NUM*MAX_NUM); 44 addx = vector<int>{ 1,-1,0,0 }; 45 addy = vector<int>{ 0,0,-1,1 }; 46 for (int i = 0; i < grid.size(); i++) { 47 for (int j = 0; j < grid[0].size(); j++) { 48 if (grid[i][j] == 0) { 49 check(i, j, grid); 50 } 51 } 52 } 53 54 set<int> s; 55 56 for (int i = 0; i < grid.size(); i++) { 57 for (int j = 0; j < grid[0].size(); j++) { 58 if (grid[i][j] == 0) { 59 int idx = i * grid[0].size() + j; 60 s.insert(get(idx)); 61 } 62 } 63 } 64 65 //从统计的并查集 删除与边沿有关的陆地 66 for (int i = 0; i < grid.size(); i++) { 67 for (int j = 0; j < grid[0].size(); j++) { 68 if (grid[i][j] == 0 && (i == 0 || i == grid.size() - 1 || j == 0 || j == grid[0].size() - 1)) { 69 int idx = i * grid[0].size() + j; 70 s.erase(get(idx)); 71 } 72 } 73 } 74 75 return s.size(); 76 } 77 78 };