leetcode 200 岛屿数量 (DFS/BFS/union-find)

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1

使用DFS遍历每个值==1的岛屿位置，一次从头的DFS把值==1的岛屿转化为‘0’下次不再重复遍历，这样DFS的次数就是岛屿的数量.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        n=len(grid)
        m=len(grid[0])
        def dfs(grid,i,j):
            if 0<=i<=n-1 and 0<=j<=m-1 and grid[i][j]=='1':
                grid[i][j]='0'
                dfs(grid,i+1,j)
                dfs(grid,i,j-1)
                dfs(grid,i-1,j)
                dfs(grid,i,j+1)
        count=0
        for i in range(n):
            for j in range(m):
                if  grid[i][j]=='1':
                    dfs(grid,i,j)
                    count+=1
        return count

使用BFS是类似的相同的思路，BFS的次数是岛屿数量

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        n=len(grid)
        if n==0:
            return 0
        m=len(grid[0])
        count=0
        for i in range(n):
            for j in range(m):
                if grid[i][j]=='1':
                    count+=1
                    grid[i][j]='0'
                    q=collections.deque([(i,j)])
                    while q:
                        row,col=q.popleft()
                        for x,y in [(row-1,col),(row,col+1),(row+1,col),(row,col-1)]:
                            if 0<=x<n and 0<=y<m and grid[x][y]=='1':
                                q.append((x,y))
                                grid[x][y]='0'
        return count

使用并查集的思路更加清晰，可能实现并查集的三个操作略微麻烦一些

class UnionFind:
    def __init__(self,grid):
        n=len(grid)
        m=len(grid[0])
        self.parent=[-1]*(n*m)
        self.value=[1]*(n*m)
        self.count=0
        for i in range(n):
            for j in range(m):
                if grid[i][j]=='1':
                    self.parent[i*m+j]=i*m+j
                    self.count+=1
    def find(self,i):
        if self.parent[i]!=i:
            self.parent[i] =self.find(self.parent[i])
        return self.parent[i]
    def union(self,x,y):
        rx=self.find(x)
        ry=self.find(y)
        if rx!=ry:
            if self.value[rx]<self.value[ry]:
                self.parent[ry]=rx
                self.value[rx]+=self.value[ry]
            if self.value[rx]>self.value[ry]:
                self.parent[rx]=ry
                self.value[ry]+=self.value[rx]
            if self.value[rx]==self.value[ry]:
                self.value[rx]+=1
                self.parent[rx]=ry
            self.count-=1
    def getCount(self):
        return self.count
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        n=len(grid)
        if n==0:
            return 0
        m=len(grid[0])
        uf=UnionFind(grid)
        for i in range(n):
            for j in range(m):
                if grid[i][j]=='1':
                    grid[i][j]='0'
                    for x,y in [(i-1,j),(i,j+1),(i+1,j),(i,j-1)]:
                        if 0<=x<n and 0<=y<m and grid[x][y]=='1':
                            uf.union(x*m+y,i*m+j)
        return uf.getCount()