最近一字节离职员工找工作，面试机会很少，被网友呛：没给你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算法文档 。
热门跟贴