【DFS】1254. 统计封闭岛屿的数目

1254. 统计封闭岛屿的数目

解题思路

• 封闭岛屿就是上下左右全部被1包围的0 也就是靠边的0不算做封闭岛屿
• 首先将上下左右的边界上的岛屿全部变成海洋
• 然后在对剩下的岛屿进行DFS遍历

class Solution {public int closedIsland(int[][] grid) {// 封闭岛屿就是上下左右全部被1包围的0  也就是靠边的0不算做封闭岛屿// 计算封闭岛屿的数量int m = grid.length;int n = grid[0].length;for(int i = 0; i < n; i++){// 将上下的岛屿 全部变成海洋// 第0行的所有列dfs(grid,0,i);// 最后一行的所有列dfs(grid,m - 1,i);}// 将左右变成海洋for(int j = 0; j < m; j++){dfs(grid,j,0);dfs(grid,j,n - 1);}// 遍历剩下的岛屿int res = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 0){res++;dfs(grid,i,j);}}}return res;}// DFS遍历void dfs(int[][] grid,int i,int j){int m = grid.length;int n = grid[0].length;if(i < 0 || j < 0 || i >= m || j >= n){return;}if(grid[i][j] == 1){return;// 如果已经遍历到海水}// 遍历到岛屿 变成1if(grid[i][j] == 0){grid[i][j] = 1;}dfs(grid,i + 1,j);dfs(grid,i,j + 1);dfs(grid,i - 1,j);dfs(grid,i,j - 1);}
}