[LeetCode] 1254. Number of Closed Islands 统计封闭岛屿的数目

2021年11月23日 阅读数:3
这篇文章主要向大家介绍[LeetCode] 1254. Number of Closed Islands 统计封闭岛屿的数目,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Given a 2D grid consists of 0s (land) and 1s (water).  An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.html

Return the number of closed islands.git

Example 1:github

Input: 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]]
Output: 2
Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:数组

Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1

Example 3:函数

Input: grid = [[1,1,1,1,1,1,1],
               [1,0,0,0,0,0,1],
               [1,0,1,1,1,0,1],
               [1,0,1,0,1,0,1],
               [1,0,1,1,1,0,1],
               [1,0,0,0,0,0,1],
               [1,1,1,1,1,1,1]]
Output: 2

Constraints:code

  • 1 <= grid.length, grid[0].length <= 100
  • 0 <= grid[i][j] <=1

这道题给了一个只包含0和1的二维数组 grid,说是0表明陆地,1表明海洋,如今定义了被海洋上下左右包围的陆地为岛屿,如今问有多少个岛屿,注意岛屿必须被海洋彻底包围,和边界相连的陆地不算是岛屿。既然岛屿是多个为0相连而造成的,那么确定是要用 BFS 或 DFS 来找到连通区域的,难点是怎么肯定找到的连通区域是否是一个岛屿,关键在于若某个连通区域和边界相连了,则其就不是岛屿了。咱们能够反过来操做一下,首先把全部和边界相连的连通区域都找出来并标记,这样以后再找到的连通区域就必定是岛屿了。因此先遍历一遍数组,遇到边界上的陆地,则开始 DFS 遍历,并标记连通区域,完成了以后,再次遍历一遍数组,遇到边界上的陆地,则开始 DFS 遍历,并标记连通区域,此时找到一个连通区域以后就能够增长岛屿的个数了,参见代码以下:htm


解法一:blog

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int res = 0, m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 0) {
                    dfs(grid, i, j);
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] != 0) continue;
                dfs(grid, i, j);
                ++res;
            }
        }
        return res;
    }
    void dfs(vector<vector<int>>& grid, int i, int j) {
        int m = grid.size(), n = grid[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != 0) return;
        grid[i][j] = 2;
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
};

咱们也能够只遍历一次,在递归函数里作些改动从而区分是否为岛屿,此时让 dfs 函数具备返回值,返回0表示不是岛屿,返回1表示是岛屿。在递归函数中,若越界了,则返回0,表示直接跟边界相连了,确定不是岛屿,不然若当前数值大于0了,表示要么遇到海洋了,要么是以前已经遍历过了,返回1。不然标记当前位置为2(标记成1也行,没太大影响),而后对四个邻居位置分别调用递归,并把四个结果乘起来,这里的乘法操做是精髓,由于只要其中有一个是0(遇到边界了),结果就是0了,表示不是岛屿。这里的相乘操做也能够替换为位运算的相'与'的操做 &,但注意必定不能用逻辑运算的'且'操做 &&,由于这个会短路后面的递归调用,从而可能致使连通区域没法被彻底标记,参见代码以下:递归


解法二:leetcode

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int res = 0, m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) res += dfs(grid, i, j);
            }
        }
        return res;
    }
    int dfs(vector<vector<int>>& grid, int i, int j) {
        int m = grid.size(), n = grid[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n) return 0;
        if (grid[i][j] > 0) return 1;
        grid[i][j] = 2;
        return dfs(grid, i + 1, j) * dfs(grid, i - 1, j) * dfs(grid, i, j + 1) * dfs(grid, i, j - 1);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1254


参考资料:

https://leetcode.com/problems/number-of-closed-islands/

https://leetcode.com/problems/number-of-closed-islands/discuss/425150/JavaC%2B%2B-with-picture-Number-of-Enclaves

https://leetcode.com/problems/number-of-closed-islands/discuss/426294/JavaPython-3-DFS-BFS-and-Union-Find-codes-w-brief-explanation-and-analysis.


LeetCode All in One 题目讲解汇总(持续更新中...)