1254. 统计封闭岛屿的数目(BFS)

1254. 统计封闭岛屿的数目

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

请返回 封闭岛屿 的数目。

示例 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

提示：

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

 1 class Solution{
 2 public:
 3     bool isInArea(int x, int y) {
 4         return (x >= 0 && x < row && y >= 0 && y < col);
 5     }
 6     void bfs(vectorint>> &grid, int x, int y) {
 7         if (!isInArea(x, y) || grid[x][y] != 0) {
 8             return;
 9         }
10         queueint, int>> q;
11         q.push(make_pair(x, y));
12         grid[x][y] = 1;
13         while (!q.empty()) {
14             int curX = q.front().first;
15             int curY = q.front().second;
16             q.pop();
17             for (auto &direction : g_direction) {
18                 int nextX = curX + direction[0];
19                 int nextY = curY + direction[1];
20                 if (isInArea(nextX, nextY) && grid[nextX][nextY] == 0) {
21                     q.push(make_pair(nextX, nextY));
22                     grid[nextX][nextY] = 1;
23                 }
24             }
25         }
26     }
27     int closedIsland(vectorint>>& grid) {
28         row = grid.size();
29         col = grid[0].size();
30         // 1、将边界及其相邻的土地(0)修改为水(1)
31         // 左、右边界及其相邻土地修改为水域
32         for (int i = 0; i < row; i++) {
33             bfs(grid, i, 0); 
34             bfs(grid, i, col - 1); 
35         }
36         // 上、下边界及其相邻土地修改为水域
37         for (int j = 0; j < col; j++) {
38             bfs(grid, 0, j); 
39             bfs(grid, row - 1, j); 
40         }
41         // 2、BFS遍历矩阵,以土地(0)为起点将土地刷新为水域,找出封闭岛屿
42         int cnt = 0;
43         for (int i = 0; i < row; i++) {
44             for (int j = 0; j < col; j++) {
45                 if (grid[i][j] == 0) {
46                     bfs(grid, i, j);
47                     cnt++;
48                 }
49             }
50         }
51         return cnt;
52     }
53 private:
54     int row;
55     int col;
56     vectorint>> g_direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
57 };