【leetcode】岛屿问题 (并查集unionfind+dfs+bfs)---更新中-爱代码爱编程
岛屿问题(难度中等)
统计封闭岛屿的数目
二维矩阵 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)