统计封闭岛屿的数目【LC1254】
二维矩阵
grid由0（土地）和1（水）组成。岛是由最大的4个方向连通的0组成的群，封闭岛是一个完全由1包围（左、上、右、下）的岛。请返回 封闭岛屿 的数目。
边界判断
- 思路
从矩阵中的每一个土地格子出发，dfs搜索连通块，如果当前岛屿对应的连通块延伸到了矩阵的边界，那么说明该岛屿不是封闭岛，返回0；如果未触及到边界，说明是封闭岛，返回1。
- 在遍历过程中，为了避免重复访问，在遍历的过程中将遍历过的土地标记为1
- 实现
class Solution { int m, n; int[][] grid; int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; public int closedIsland(int[][] grid) { m = grid.length; n = grid[0].length; this.grid = grid; int res = 0; for (int i = 1; i < m; i++){ for (int j = 1; j < n; j++){ if (grid[i][j] == 0){ res += dfs(i , j); } } } return res; } public int dfs(int i, int j){ int flag = 1; if (grid[i][j] == 0){ if (i == m - 1 || i == 0 || j == n - 1 || j == 0) return 0; grid[i][j] = 1; for (int k = 0; k < 4; k++){ int x = i + dirs[k][0], y = j + dirs[k][1]; if (x >= 0 && x < m && y >= 0 && y < n){ flag = (flag & dfs(x, y)); } } } return flag; } }
先外后内
- 思路：
先对与边界相连的土地标记为1，那么剩下的岛屿均为封闭岛 - 实现
class Solution { public int closedIsland(int[][] grid) { int m = grid.length, n = grid[0].length; for (int i = 0; i < m; i++) { // 如果是第一行和最后一行，访问所有格子 // 如果不是，只访问第一列和最后一列的格子 int step = i == 0 || i == m - 1 ? 1 : n - 1; for (int j = 0; j < n; j += step) dfs(grid, i, j); } int ans = 0; for (int i = 1; i < m - 1; i++) { for (int j = 1; j < n - 1; j++) { if (grid[i][j] == 0) { // 从没有访问过的 0 出发 ans++; // 一定是封闭岛屿 dfs(grid, i, j); } } } return ans; } private void dfs(int[][] grid, int x, int y) { if (x < 0 || x >= grid.length || y < 0 || y >= grid[x].length || grid[x][y] != 0) return; grid[x][y] = 1; // 标记 (x,y) 被访问，避免重复访问 dfs(grid, x - 1, y); dfs(grid, x + 1, y); dfs(grid, x, y - 1); dfs(grid, x, y + 1); } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/number-of-closed-islands/solutions/2312616/liang-chong-si-lu-xian-wai-hou-nei-chu-j-b1e4/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
