[LeetCode] 1254. Number of Closed Islands

Given a 2D grid consists of 0s (land) and 1s (water).  An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example 1:

Input: 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]]
Output: 2
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1

Example 3:

Input: 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]]
Output: 2

Constraints:

• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <=1

统计封闭岛屿的数目。

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。

请返回 封闭岛屿 的数目。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-closed-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路还是跟岛屿类型的题一样，用 BFS 或者 DFS 做，需要遍历 input 矩阵两遍。BFS 或者 DFS 做时间空间复杂度相同。

注意这道题的规则，在 grid 边缘上的 0 是无法被完全包围的，所以我们第一轮遍历的时候先要把这些 0 变成 1。第二轮扫描的时候，剩下的 0 才是四面都被 1 包围的 0。

时间O(mn)

空间O(mn)

BFS

 1 class Solution {
 2     int m;
 3     int n;
 4     int[] dx = {-1, 1, 0, 0};
 5     int[] dy = {0, 0, -1, 1};
 6     
 7     public int closedIsland(int[][] grid) {
 8         m = grid.length;
 9         n = grid[0].length;
10         // 把边界上所有的0变成1
11         for (int i = 0; i < m; i++) {
12             for (int j = 0; j < n; j++) {
13                 if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 0) {
14                     bfs(grid, i, j);
15                 }
16             }
17         }
18 
19         int count = 0;
20         for (int i = 0; i < m; i++) {
21             for (int j = 0; j < n; j++) {
22                 if (grid[i][j] == 0) {
23                     count++;
24                     bfs(grid, i, j);
25                 }
26             }
27         }
28         return count;
29     }
30     
31     private void bfs(int[][] grid, int i, int j) {
32         Queue<int[]> queue = new LinkedList<>();
33         queue.offer(new int[] { i, j });
34         while (!queue.isEmpty()) {
35             int[] cur = queue.poll();
36             int x = cur[0];
37             int y = cur[1];
38             grid[x][y] = 1;
39             for (int k = 0; k < 4; k++) {
40                 int newX = x + dx[k];
41                 int newY = y + dy[k];
42                 if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 0) {
43                     queue.offer(new int[] { newX, newY });
44                 }
45             }
46         }
47     }
48 }

DFS

 1 class Solution {
 2     int m;
 3     int n;
 4 
 5     public int closedIsland(int[][] grid) {
 6         m = grid.length;
 7         n = grid[0].length;
 8         for (int i = 0; i < m; i++) {
 9             for (int j = 0; j < n; j++) {
10                 // 处理边界上的0
11                 if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 0) {
12                     dfs(grid, i, j);
13                 }
14             }
15         }
16         
17         int count = 0;
18         for (int i = 0; i < m; i++) {
19             for (int j = 0; j < n; j++) {
20                 if (grid[i][j] == 0) {
21                     count++;
22                     dfs(grid, i, j);
23                 }
24             }
25         }
26         return count;
27     }
28 
29     private void dfs(int[][] grid, int i, int j) {
30         if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 1) {
31             return;
32         }
33         grid[i][j] = 1;
34         dfs(grid, i - 1, j);
35         dfs(grid, i + 1, j);
36         dfs(grid, i, j - 1);
37         dfs(grid, i, j + 1);
38     }
39 }

flood fill题型总结

LeetCode 题目总结