leetcode：1020. 飞地的数量

题目

给你一个大小为 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 没有被包围，因为它在边界上。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-enclaves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 2：

输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。

解答 & 代码

[中等] 1254. 统计封闭岛屿的数目
本题思路和上题基本相同
只有靠边界的岛屿（即存在某个格子在边界上的岛屿）才是可到达的，剩余的岛屿格子都是不可到底的飞地。
因此，只需要先将靠边界的岛屿淹掉（都变为 0），在统计剩余的陆地单元格（1）的个数，就是飞地数量

class Solution {
private:
    // 深度优先搜索，将当前岛屿淹没。即从位置 (row, col) 开始，将与之相邻的都置 0（即变为海水）
    void dfs(vector<vector<int>>& grid, int row, int col)
    {
        int rows = grid.size();
        int cols = grid[0].size();
        // 递归结束条件：越界 or 已经是海水
        if(row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == 0)
            return;
        // 将 (row, col) 位置置 0（即变为海水）
        grid[row][col] = 0;
        // 递归搜索上、下、左、右，将当前岛屿的每个位置都变为 1（即变为海水）
        dfs(grid, row - 1, col);
        dfs(grid, row + 1, col);
        dfs(grid, row, col - 1);
        dfs(grid, row, col + 1);
    }
public:
    int numEnclaves(vector<vector<int>>& grid) {
        if(grid.size() == 0 || grid[0].size() == 0)
            return 0;
        int rows = grid.size();
        int cols = grid[0].size();

        // 去掉靠上、下、左、右边界的岛屿（置为 0，相当于淹掉）
        for(int col = 0; col < cols; ++col)
        {
            dfs(grid, 0, col);            // 靠上边界的岛屿淹掉（变为海水 0）
            dfs(grid, rows - 1, col);    // 靠下边界的岛屿淹掉（变为海水 0）
        }
        for(int row = 0; row < rows; ++row)
        {
            dfs(grid, row, 0);            // 靠左边界的岛屿淹掉（变为海水 0）
            dfs(grid, row, cols - 1);    // 靠右边界的岛屿淹掉（变为海水 0）
        }

        // 剩下的陆地单元格（为 1 的格子）都是无法到达的飞地
        // 因此统计剩下的值为 1 的格子的个数即可
        int cnt = 0;
        for(int row = 0; row < rows; ++row)
        {
            for(int col = 0; col < cols; ++col)
            {
                if(grid[row][col] == 1)
                    ++cnt;
            }
        }
        return cnt;
    }
};

复杂度分析：设矩阵 M 行 N 列

• 时间复杂度 O(MN)
• 空间复杂度 O(MN)：在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN，即空间复杂度达到 O(MN)

执行结果：

执行结果：通过

执行用时：36 ms, 在所有 C++ 提交中击败了 99.66% 的用户
内存消耗：21.1 MB, 在所有 C++ 提交中击败了 86.83% 的用户