# LeetCode: 1254. 统计封闭岛屿的数目¶

## 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]]



输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]

[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]]



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

## 2、解题思路¶

• 使用并查集
• 将所有的水以及靠边的陆地都放到同一个集合中
• 最后统计集合数量减一即可

class DFU:
def __init__(self, length):
self.data = list(range(length))

def find(self, x):
if self.data[x] != x:
self.data[x] = self.find(self.data[x])
return self.data[x]

def union(self, x, y):
xp = self.find(x)
yp = self.find(y)
if xp != yp:
if xp > yp:
self.data[yp] = xp
else:
self.data[xp] = yp

def count(self):
res = 0
for index, i in enumerate(self.data):
if index == i:
res += 1
return res

class Solution:
def closedIsland(self, grid: List[List[int]]) -> int:
row, col = len(grid), len(grid[0])
length = row * col
d = DFU(length + 1)
# 上下左右-坐标
surround = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 坐标验证
def available(m, n):
return 0 <= m < row and 0 <= n < col

for r, row_line in enumerate(grid):
for c, item in enumerate(row_line):
if item == 1 or r in [0, row - 1] or c in [0, col - 1]:
d.union(length, r * col + c)
else:
for dx, dy in surround:
nr, nc = r + dx, c + dy
if available(nr, nc) and grid[nr][nc] == 0:
d.union(r * col + c, nr * col + nc)
return d.count() - 1