LeetCode_DFS_中等_1020.飞地的数量

缺乏、安全感 2023-10-06 22:32 13阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

**返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。**

**示例 1：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu_size_8_color_FFFFFF_t_70_g_se_x_16]  
输入：grid = \[\[0,0,0,0\],\[1,0,1,0\],\[0,1,1,0\],\[0,0,0,0\]\]  
输出：3  
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

**示例 2：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu_size_8_color_FFFFFF_t_70_g_se_x_16 1]  
输入：grid = \[\[0,1,1,0\],\[0,0,1,0\],\[0,0,1,0\],\[0,0,0,0\]\]  
输出：0  
解释：所有 1 都在边界上或可以到达边界。

**提示：**  
m == grid.length  
n == grid\[i\].length  
1 <= m, n <= 500  
grid\[i\]\[j\] 的值为 0 或 1

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/number-of-enclaves

## 2.思路 ##

（1）DFS  
这题属于岛屿系列问题，岛屿系列问题的基本思路框架是 [LeetCode\_DFS\_中等\_200.岛屿数量][LeetCode_DFS_200.]这道题。这道题和 [LeetCode\_DFS\_中等\_1254. 统计封闭岛屿的数目][LeetCode_DFS_1254.]这题基本⼀样，只不过那题要计算封闭岛屿的数量，而本题要计算这些封闭岛屿的陆地总数，所以在那题的基础上将代码稍作修改即可。

## 3.代码实现（Java） ##

//思路1————DFS
    class Solution {
        
        public int numEnclaves(int[][] grid) {
        
            //res保存封闭岛屿的陆地数量，初始值为 0
            int res = 0;
            int m = grid.length;
            int n = grid[0].length;
            for (int i = 0; i < m; i++) {
        
                //把grid中靠左边的岛屿淹没掉
                dfs(grid, i, 0);
                //把grid中靠右边的岛屿淹没掉
                dfs(grid, i, n - 1);
            }
            for (int i = 0; i < n; i++) {
        
                //把grid中靠上边的岛屿淹没掉
                dfs(grid, 0, i);
                //把grid中靠下边的岛屿淹没掉
                dfs(grid, m - 1, i);
            }
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (grid[i][j] == 1) {
        
                        res++;
                    }
                }
            }
            return res;
        }
    
        public void dfs(int[][] grid, int i, int j) {
        
            int m = grid.length;
            int n = grid[0].length;
            //处理边界条件
            if (i < 0 || j < 0 || i >= m || j >= n) {
        
                return;
            }
            if (grid[i][j] == 0) {
        
                return;
            }
            grid[i][j] = 0;
            //同时也淹没上下左右的陆地
            dfs(grid, i - 1, j);
            dfs(grid, i + 1, j);
            dfs(grid, i, j - 1);
            dfs(grid, i, j + 1);
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu_size_8_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/804efea9812f402faf3dd62a91f3da0d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu,size_8,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu_size_8_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/2a7ef18c98ae43b384e637352d19c2f9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu,size_8,color_FFFFFF,t_70,g_se,x_16
[LeetCode_DFS_200.]: https://blog.csdn.net/weixin_43004044/article/details/124337167
[LeetCode_DFS_1254.]: https://blog.csdn.net/weixin_43004044/article/details/124337019