代码编织梦想

统计封闭岛屿的数目

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/number-of-closed-islands

解法1:UnionFind

from collections import deque

def find(root, x):
    if x == root[x]:
        return root[x]
    else:
        return find(root, root[x])

def union(root, x, y):
    root_x = find(root, x)
    root_y = find(root, y)
    if root_x != root_y:
        root[root_y] = root_x

def closedIsland(grid) -> int:
    row = len(grid)
    col = len(grid[0])
    count = row * col
    root = [i for i in range(count)]
    waters = 0  # 水个数
    border_island = 0  # 边界岛个数
    union_times = 0  # 合并次数
    q = deque()  # 循环土地队列
    is_border = False  # 当前循环的土地是否在边界上

    for r in range(row):
        for l in range(col):
            if grid[r][l] == 1:  # 水
                waters += 1
                continue
            else:  # 地
                if r * col + l == root[r * col + l]:  # 没有合并
                    q.append((r, l))
                    while q:
                        spot = q.popleft()
                        li = [
                              (spot[0] - 1, spot[1]), (spot[0], spot[1] - 1),
                            (spot[0], spot[1] + 1), (spot[0] + 1, spot[1])
                        ]  # 上下左右
                        for s in li:
                            if 0 <= s[0] < row and 0 <= s[1] < col and grid[s[0]][s[1]] == 0\
                                    and root[r * col + l] != root[s[0] * col + s[1]]:
                                    # and (s[0] * col + s[1] == root[s[0] * col + s[1]]):      #TODO: 增加一个映射到root的函数
                                if s[0] * col + s[1] == root[s[0] * col + s[1]]:    # 祖先为自己
                                    union(root, r * col + l, s[0] * col + s[1])
                                    q.append(s)
                                    # union_times += 1
                                else:   # 祖先不为自己,已到达过
                                    union(root, s[0] * col + s[1], r * col + l)  # rl的祖先跟随s
                                    border_island -= 1  # 不需要加边界岛屿,因为已经算过了,下面会多算一次所以要减掉
                                union_times += 1

                                if s[0] == row - 1 or s[1] == col - 1 or s[0] == 0 or s[1] == 0:  # 边界
                                    is_border = True

                    if is_border or (r == row - 1 or l == col - 1 or r == 0 or l == 0):  # 后面两个条件为 处于单独一个边界土地的情况
                        border_island += 1
                        is_border = False  # 此岛循环结束
    return count - waters - union_times - border_island

解法2:

class Solution:
    def __init__(self):
        self.m = 0
        self.n = 0
    def closedIsland(self, grid) -> int:
        """
        不封闭的岛屿一定是经过矩形的边的,所以可以先将位于边上的岛屿先变成海水。
        (即不统计边上岛屿的数量)
        """
        self.m = len(grid)
        self.n = len(grid[0])
        res = 0

        # 先将靠上下的岛屿改为海水
        for j in range(self.n):
            self.dfs(grid, 0, j)
            self.dfs(grid, self.m-1, j)

        # 将靠左右两边的岛屿改为海水
        for i in range(self.m):
            self.dfs(grid, i, 0)
            self.dfs(grid, i, self.n-1)

        # 剩余的岛屿就是封闭岛屿了,开始统计
        for i in range(self.m):
            for j in range(self.n):
                if grid[i][j] == 0:
                    res += 1
                    self.dfs(grid, i, j)

        return res

    def dfs(self, grid, i, j):
        if i<0 or j<0 or i>=self.m or j>=self.n:
            return
        if grid[i][j]==1:
            # 已经变成海水了,不用继续向下遍历了。
            return

        grid[i][j] = 1
        self.dfs(grid, i, j+1)
        self.dfs(grid, i, j-1)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i+1, j)
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45068714/article/details/129828684

DFS & BFS& 并查集 -leetcode-200. 岛屿数量-爱代码爱编程

200. 岛屿数量 题目描述 本题就是求 图中 连通分量的个数 求图中 连通分量个数的方法(3 种): DFSBFS并查集 DFS 使用标记数组 使用 visited 标记数组,保证图中每个顶点不会

【leetcode】200. 岛屿数量(并查集/ bfs/ dfs)_零下3℃的博客-爱代码爱编程

题目: 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。 输入: 11110 11010 11000 00000 输出: 1 解题思路: DFS,记录启动DFS的次数BFS,记录启动BFS次数并查集,对相邻陆

day 25-26 算法:并查集、岛屿的个数、朋友圈问题_听风丨说话的博客-爱代码爱编程

两个题解法其实是一致的,当多练一遍 1. 题目 给定一个由’1’(陆地)和’0’(水)组成的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或者垂直方向相邻的陆地连接而成。你可以假设网格的四个边均

leetcode--朋友圈(深度优先搜索+广度优先搜索+并查集)-爱代码爱编程

                                               朋友圈 班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。   给定一个 N * N 的矩阵 M,表示班级中学

leetcode--岛屿数量(bfs dfs 并查集)-爱代码爱编程

                                            岛屿数量 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。 示例 1: 输入: 11110 11010 11000 0000

LeetCode200.岛屿数量dfs/bfs/并查集 java-爱代码爱编程

题目描述 给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。 示例 1: 输入: 11110 11010 11000 00000 输出: 1 示例 2: 输入: 11000 11000 00100 00011 输

Leetcode200-岛屿数量,一道经典题目区分BFS和DFS,理解并查集-爱代码爱编程

本文参考岛屿数量 问题描述 给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。 示例1: 输入: 11110 11010 11000 00000 输出: 1 示例2:

leetcode200--c++解答(dfs+bfs+并查集)-爱代码爱编程

题目 给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。 示例 1: 输入: 11110 11010 11000 00000 输出: 1 示例 2: 输入: 11000 11000

算法-图/DFS/BFS/并查集-岛屿数量-爱代码爱编程

算法-图/DFS/BFS/并查集-岛屿数量 1 题目概述 1.1 题目出处 https://leetcode-cn.com/problems/number-of-islands 1.2 题目描述 给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的

【LeetCode】200.岛屿数量(dfs+bfs+并查集,超详细图文解释)-爱代码爱编程

题目 分析 说明:以下介绍的算法,除了并查集以外,DFS 和 BFS 都属于很基础的算法内容,也非常好理解,写法也相对固定,读者需要多写,发现并记录自己的问题,我也是在写了几遍甚至是在写本题解的过程中,才发现出自己的问题。 这道题是可以使用一个经典的算法来解决的,那就是 Flood fill,以下的定义来自 维基百科:Flood fill 词

LeetCode 岛屿数量(200题)DFS、BFS、并查集-爱代码爱编程

LeetCode 岛屿数量 @author:Jingdai @date:2020.12.29 题目描述(200题) 给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。 示例

LeetCode200 :岛屿数量(DFS+BFS+并查集)-爱代码爱编程

LeetCode200.岛屿数量 这是一道求连通块个数的题,是一道dfs模板题。 DFS class Solution { public: int m,n;//m行n列 bool board(int x,int y) { if((x>=0)&&(y>=0)&&(x<

【力扣200. 岛屿数量 305. 岛屿数量 II】DFS+BFS+并查集、并查集(python3)-爱代码爱编程

目录 题目描述思路题解200. 岛屿数量dfsbfs并查集305. 岛屿数量 II 题目描述 200. 岛屿数量/305. 岛屿数量 II 思路题解 200. 岛屿数量 https://leetcode-cn.com/problems/number-of-islands/solution/number-of-islands-shen-d

LeetCode200---岛屿数量的三种解法(DFS、BFS、并查集)-爱代码爱编程

LeetCode200---岛屿数量 前言一、DFS解法1.1 DFS介绍二、BFS解法2.1 BFS介绍三、Union Find解法3.1 Union Find介绍总结 前言 解题思路链接   题目要求: 给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/

DFS - leetcode-岛屿问题(合集)-爱代码爱编程

在 leetcode 上写 DFS 时,看到了 nettee 老哥的-DFS 框架,于是写了几道 岛屿问题 练练手 岛屿问题: 200. 岛屿数量 三种解法:DFS、BFS、并查集(这里主要记录 DFS)463. 岛屿的周长695. 岛屿的最大面积827. 最大人工岛 200. 岛屿数量 本质上就是 求图中 连通分量的个数 求图中

Leetcode-DFS/BFS算法-爱代码爱编程

200-岛屿数量 给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。 解题思路 方法一:深度优先搜索 我们可以将二维网格看成一个无向图,竖直或水平相邻的 1 之间有边相连。 为了求出岛屿

leetcode刷题 200. 岛屿数量 Medium Java DFS+BFS+并查集-爱代码爱编程

1.题目描述 给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。 示例 1: 输入: grid = [ [“1”,“1”,“1”,“1”,“0”], [“1”,“1”,“0

leetcode刷题 547. 省份数量 Medium Java DFS+BFS+并查集-爱代码爱编程

这题可以和# 200. 岛屿数量一起写。 1.题目描述 有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。 省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。 给你一个 n x n 的矩阵 isConnected ,其中 isCon