图论06-飞地的数量(Java)

6.飞地的数量

• 题目描述

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

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

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

示例 1：

输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

• 题目分析

1.题目分析
给定一个二进制矩阵 grid，其中0表示海洋单元格，1表示陆地单元格。
一次移动是指从一个陆地单元格走到另一个相邻的陆地单元格或者跨过矩阵边界。
要求找出在任意次数的移动中无法离开网格边界的陆地单元格数量。

2.思路分析
--主要思路：
使用深度优先搜索（DFS）来遍历所有的陆地单元格，并标记与边界相连的陆地单元格。
维护两个全局变量 flag 和 spare，分别用于标记每块岛屿是否靠海和记录每块岛屿的面积。
遍历整个二维网格，对每个陆地单元格进行DFS处理，统计无法跨越边界的方块数。

--详细步骤：
-初始化 count 为0，用于表示无法跨越边界的方块数。
-遍历二维网格 grid 的每个单元格 (i, j)：
-如果当前单元格为陆地（grid[i][j] == 1），则调用 dfs 方法进行DFS处理。
-在 dfs 方法中：
如果当前位置 (i, j) 超出边界或者是海洋（grid[i][j] == 0），则返回。否则，标记当前位置为已访问，更新 spare 记录当前岛屿面积。
如果当前位置在边界上，则将 flag 标记为1，表示当前岛屿靠近海洋。继续递归调用DFS处理当前位置的四个相邻位置。
如果当前岛屿不靠近海洋（flag == 0），则将当前岛屿的面积累加到 count 中。最后返回 count 作为结果。
-复杂度分析：
时间复杂度：O(m*n)，m 和 n 分别为二维网格的行数和列数，需要遍历整个二维网格。
空间复杂度：O(1)，除了函数调用栈外，没有使用额外空间。

• Java代码实现

class Solution {
    int flag = 0; // 用于标记每块岛屿是否靠海
    int spare = 0; // 用于标记每块岛屿的面积

    public int numEnclaves(int[][] grid) {
        int count = 0; // 表示无法跨越边界的方块数
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j);
                    if (flag == 0) {
                        count += spare;
                    }
                    spare = 0;
                    flag = 0;
                }
            }
        }
        return count;
    }

    private void dfs(int[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
            return;
        }

        if (grid[i][j] == 0) {
            return;
        }

        spare++;
        grid[i][j] = 0;
        if (i == 0 || i == grid.length - 1 || j == 0 || j == grid[0].length - 1) {
            flag = 1; // 表示存在临海区域
        }

        dfs(grid, i + 1, j); // 下
        dfs(grid, i - 1, j); // 上
        dfs(grid, i, j + 1); // 右
        dfs(grid, i, j - 1); // 左
    }
}