【力扣 096】1254. 统计封闭岛屿的数目

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

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

代码实现：

class Solution {
public:
    int dfs(vector>& grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 1) {
            return 0;
        }
        int di[4] = {-1,0,1,0};
        int dj[4] = {0,1,0,-1};
        grid[i][j] = 1;
        for (int index = 0; index < 4; ++index) {
            int next_i = i + di[index];
            int next_j = j + dj[index];
            dfs(grid, next_i,next_j);
        }
        return 1;
    } 

    void dfs_bound(vector>& grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 1) 
            return;

        int di[4] = {-1,0,1,0};
        int dj[4] = {0,1,0,-1};
        grid[i][j] = 1;
        for (int index = 0; index < 4; ++index)
        {
            int next_i = i + di[index];
            int next_j = j + dj[index];
            dfs_bound(grid, next_i,next_j);
        }
    } 

    int closedIsland(vector>& grid) {
        // 先把周围的不封闭的点处理掉
        for (int i = 0; i < grid.size(); ++i) {
            dfs_bound(grid, i, 0);
            dfs_bound(grid, i, grid[0].size() - 1);
        }
        // 先把周围的不封闭的点处理掉
        for (int j = 0; j < grid[0].size(); ++j) {
            dfs_bound(grid, 0, j);
            dfs_bound(grid, grid.size() - 1, j);
        }
        // 接下来实际就是求岛屿的数量了
        int num = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                num += dfs(grid, i, j); 
            }
        }
        return num;
    }
};