leetcode：1254. 统计封闭岛屿的数目

题目

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的 4 个方向连通的 0 组成的群，封闭岛是一个 **完全** 由 1 包围（左、上、右、下）的岛。
请返回 封闭岛屿 的数目。

示例 1：
[中等] 1254. 统计封闭岛屿的数目 - 图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. 输出：2
  3. 解释：
  4. 灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。

示例 2：
[中等] 1254. 统计封闭岛屿的数目 - 图2

  1. 输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
  2. 输出：1

示例 3：

  1. 输入：grid = [[1,1,1,1,1,1,1],
  2.              [1,0,0,0,0,0,1],
  3.              [1,0,1,1,1,0,1],
  4.              [1,0,1,0,1,0,1],
  5.              [1,0,1,1,1,0,1],
  6.              [1,0,0,0,0,0,1],
  7.              [1,1,1,1,1,1,1]]
  8. 输出：2

解答 & 代码

[中等] 200. 岛屿数量
本题是统计封闭岛屿的数量，和上题的区别在于：

  1. 本题 0 表示陆地，1 表示海水，和上题相反

  2. 封闭岛屿是上下左右都被海水（1）包围的岛屿（0），越界的地方不算海水（1），因此靠边的陆地不算岛屿（而上题越界的地方认为是海水，因此靠边的陆地也算岛屿）。更具体地，将上题的岛屿中除去靠边的岛屿，剩下的就是封闭岛屿：

    • 若某个岛屿至少有一格在上、下、左、右任意一个边界上，这个岛屿就不是封闭岛屿。因为如果有一格在上边界上，它的上方就不是海水；如果有一格在下边界上，它的下方就不是海水；如果有一格在左边界上，它的左边就不是海水；如果有一格在右边界上，它的右边就不是海水

      1. class Solution {
      2. private:
      3. // 深度优先搜索，从位置 (row, col) 开始，将与之相邻的都置 1（即变为海水）
      4. void dfs(vector<vector<int>>& grid, int row, int col)
      5. {
      6.    int rows = grid.size();
      7.    int cols = grid[0].size();
      8.    // 递归结束条件：越界 or 已经是海水
      9.    if(row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == 1)
      10.        return;
      11.    // 将 (row, col) 位置置 1（即变为海水）
      12.    grid[row][col] = 1;
      13.    // 递归搜索上、下、左、右，将当前岛屿的每个位置都变为 1（即变为海水）
      14.    dfs(grid, row - 1, col);
      15.    dfs(grid, row + 1, col);
      16.    dfs(grid, row, col - 1);
      17.    dfs(grid, row, col + 1);
      18. }
      19. public:
      20. int closedIsland(vector<vector<int>>& grid) {
      21.    if(grid.size() == 0 || grid[0].size() == 0)
      22.        return 0;
      23.    int rows = grid.size();
      24.    int cols = grid[0].size();
      26.    // 1. 去掉靠上、下、左、右边界的岛屿（置为 1，相当于淹掉）
      27.    for(int col = 0; col < cols; ++col)
      28.    {
      29.        dfs(grid, 0, col);            // 靠上边界的岛屿淹掉（变为海水 1）
      30.        dfs(grid, rows - 1, col);    // 靠下边界的岛屿淹掉（变为海水 1）
      31.    }
      32.    for(int row = 0; row < rows; ++row)
      33.    {
      34.        dfs(grid, row, 0);            // 靠左边界的岛屿淹掉（变为海水 1）
      35.        dfs(grid, row, cols - 1);    // 靠右边界的岛屿淹掉（变为海水 1）
      36.    }
      38.    // 2. 剩下的都是封闭岛屿，统计封闭岛屿个数
      39.    int islandCnt = 0;
      40.    for(int row = 1; row < rows - 1; ++row)
      41.    {
      42.        for(int col = 1; col < cols - 1; ++col)
      43.        {
      44.            if(grid[row][col] == 0)
      45.            {
      46.                ++islandCnt;
      47.                dfs(grid, row, col);
      48.            }
      49.        }
      50.    }
      51.    return islandCnt;
      52. }
      53. };

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

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

执行结果：

  1. 执行结果：通过
  3. 执行用时：12 ms, 在所有 C++ 提交中击败了 61.37% 的用户
  4. 内存消耗：9.2 MB, 在所有 C++ 提交中击败了 61.56% 的用户