字节大佬找工作被呛：没给你3d接雨水已经是放过你了。。。

最近一字节离职员工找工作，面试机会很少，被网友呛：没给你3d接雨水已经是放过你了。接雨水是LeetCode上的两道题，一道是 2 维的一道是 3 维的，这两道题都是Hard级别，相对于其他题来说是有一定难度，如果搞懂原理之后也没那么难，我之前写过，可以看下：

网友评论：

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第1254：统计封闭岛屿的数目。

问题描述

来源：LeetCode第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

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

• 0 <= grid[i][j] <=1

问题分析

这题让计算岛屿的数量，0 是土地，可以构成岛屿，1 是水，其中 岛屿必须被水包围 。

我们可以使用DFS来解这道题，遍历二维数组，如果是 1 (水) 就跳过，如果是 0 (土地)，说明 有可能是岛屿 。我们需要沿着它的上下左右 4 个方向遇到土地的要全部把它变成水。

注意岛屿不能延伸到矩阵的边界，因为岛屿必须被水包围的，而边界上的位置是没法被包围的。

JAVA：

public int closedIsland(int[][] grid) {
    int ans = 0; // 岛屿的数量
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            // 如果是0，说明是陆地，然后在计算
            if (grid[i][j] == 0)
                ans += dfs(grid, i, j);
        }
    }
    return ans;
}

private int dfs(int[][] land, int i, int j) {
    // 如果到边界了，并且边界是陆地，说明这一连串陆地没有被水给包围，不是岛屿，直接返回0
    if ((i == 0 || i == land.length - 1 || j == 0 ||
            j == land[0].length - 1) && land[i][j] == 0)
        return 0;
    if (land[i][j] == 1) // 如果当前区域是水域，就返回 1
        return 1;
    int count = 1;
    // 表示已经被统计过了，防止重复统计。
    land[i][j] = 1;
    // 然后沿着当前水域的上下左右4个方向继续查找。
    count &= dfs(land, i - 1, j);// 上
    count &= dfs(land, i + 1, j);// 下
    count &= dfs(land, i, j - 1);// 左
    count &= dfs(land, i, j + 1);// 右
    return count;
}

C++：

public:
    int closedIsland(vector

 > &grid) {         int ans = 0; // 岛屿的数量         for (int i = 0; i < grid.size(); i++) {             for (int j = 0; j < grid[0].size(); j++) {                 // 如果是0，说明是陆地，然后在计算                 if (grid[i][j] == 0)                     ans += dfs(grid, i, j);             }         }         return ans;     }     int dfs(vector

 > &grid, int i, int j) {         // 如果到边界了，并且边界是陆地，说明这一连串陆地没有被水给包围，不是岛屿，直接返回0         if ((i == 0 || i == grid.size() - 1 || j == 0 ||              j == grid[0].size() - 1) && grid[i][j] == 0)             return 0;         if (grid[i][j] == 1) // 如果当前区域是水域，就返回 1             return 1;         int count = 1;         // 表示已经被统计过了，防止重复统计。         grid[i][j] = 1;         // 然后沿着当前水域的上下左右4个方向继续查找。         count &= dfs(grid, i - 1, j);// 上         count &= dfs(grid, i + 1, j);// 下         count &= dfs(grid, i, j - 1);// 左         count &= dfs(grid, i, j + 1);// 右         return count;     }

Python：

def closedIsland(self, grid: List[List[int]]) -> int:
    def dfs(i, j):
        # 如果到边界了，并且边界是陆地，说明这一连串陆地没有被水给包围，不是岛屿，直接返回0
        if (i == 0 or i == len(grid) - 1 or j == 0 or j == len(grid[0]) - 1) and grid[i][j] == 0:
            return 0
        if grid[i][j] == 1:  # 如果当前区域是水域，就返回 1
            return 1
        count = 1
        # 表示已经被统计过了，防止重复统计。
        grid[i][j] = 1
        # 然后沿着当前水域的上下左右4个方向继续查找。
        count &= dfs(i - 1, j)  # 上
        count &= dfs(i + 1, j)  # 下
        count &= dfs(i, j - 1)  # 左
        count &= dfs(i, j + 1)  # 右
        return count

    ans = 0  # 岛屿的数量
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            # 如果是0，说明是陆地，然后在计算
            if grid[i][j] == 0:
                ans += dfs(i, j)
    return ans

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。