一定要早日上岸鸭 · July 30, 2021 2

1254. 统计封闭岛屿的数目

1254. 统计封闭岛屿的数目

此题是典型的岛屿问题;可以拆分为两个部分:寻找连通块已经去除边界的连通块;

此题中学到了用dx, dy来移动,并且用一个布尔数组来表示是否遍历过点来避免重复遍历;已经用flag传址来标记是否为边界上的连通块即不为封闭岛屿:代码如下:

class Solution { // 记录x和y的移动值 public static int[] dx = new int[]{-1, 1, 0, 0}; public static int[] dy = new int[]{0, 0, -1, 1}; // 记录是否之前已经遍历过这个点: public boolean[][] whether_visited ; // 存储grid到heap这样就可以随时调用; public int[][] grid; boolean flag = false; public boolean check(int nowx, int nowy, int n, int m){ return nowx>=0 && nowx<n && nowy>=0 && nowy<m; } public void dfs(int x, int y, int n, int m){ whether_visited[x][y] = true; for(int i = 0;i<4; i++){ int nowx = x + dx[i]; int nowy = y + dy[i]; if(!check(nowx, nowy, n , m)){ // 说明处于边界不算做连通块(封闭岛屿) flag = true; continue; } if(grid[nowx][nowy]==0 && !whether_visited[nowx][nowy]){ dfs(nowx, nowy, n, m); } } } public int closedIsland(int[][] grid) { this.grid = grid; int n = grid.length; int m = grid[0].length; whether_visited = new boolean[n][m]; int ans = 0; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ if(grid[i][j]==0 && !whether_visited[i][j]){ flag = false; dfs(i,j, n, m); if(!flag){ ans++; } } } } return ans; } }