200. 岛屿的个数

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

解法一：dfs

思路很直接，遍历棋盘，遇到‘1’就dfs，把访问过的地方置‘0’。统计dfs次数即可

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0  #统计岛屿数
        #遍历棋盘
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                #遇到‘1’就调用递归dfs搜索，岛屿数+1
                if grid[i][j] == '1':  
                    count += 1
                    self.dfs(grid, i, j)
                    #递归完再加也可
                    #count += 1
        return count
    
    #深度优先遍历所有‘1’，并置零
    def dfs(self, grid, i, j):
        #特别要注意边界，除了越界，还有‘0’也要返回，否则会无限重复访问
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
            return
        grid[i][j] = '0'    #访问该岛屿，并标记为0
        #上下左右
        self.dfs(grid, i-1, j)
        self.dfs(grid, i+1, j)
        self.dfs(grid, i, j-1)
        self.dfs(grid, i, j+1)

二、并查集

并查集初始化为m*n规模（每个点都是一个根），此处略作修改，连通分量个数为‘1’的数量，‘0’不计入。

遍历二维网格，遇到‘1’就尝试将上下左右的1连通，最后统计连通分量数

class UnionFind:
    # 构造函数传入totalNodes为总节点数
    def __init__(self, totalNodes, count):
        # parents[i]表示i的根，初始i的根为其自身
        self.parents = [i for i in range(totalNodes)]
        # 连通分量数
        self.count = count
        # 树的“重量”
        self.size = [1] * totalNodes
    # 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        # 不连通才合并
        if root1 != root2:
          	# 小树合并到大树
            if self.size[root1] > self.size[root2]:
                self.parents[root2] = root1
                self.size[root1] += self.size[root2]
            else:
                self.parents[root1] = root2
                self.size[root2] += self.size[root1]
            # 连通分量数减一
            self.count -= 1

    # 查找最终的根
    def find(self, node):
        while self.parents[node] != node:
            self.parents[node] = self.parents[self.parents[node]]
            node = self.parents[node]
        return node

    # 判断两个点是否连通
    def isConnected(self, node1, node2):
        return self.find(node1) == self.find(node2)

    # 返回连通分量个数
    def count(self):
        return self.count

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        #将二维坐标展平为一维
        def flat(x, y):
            return x * n + y
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
        uf = UnionFind(m*n, count) #初始：每个'1'结点都是一个连通分量
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    # 将当前1置0，减少重复合并。不置0也没错，会稍慢
                    grid[i][j] = '0'
                    #看左右上下是否存在1
                    if j > 0 and grid[i][j-1] == '1':
                        uf.union(flat(i,j), flat(i, j-1))
                    if j < n-1 and grid[i][j+1] == '1':
                        uf.union(flat(i,j), flat(i, j+1))
                    if i > 0 and grid[i-1][j] == '1':
                        uf.union(flat(i,j), flat(i-1, j))
                    if i < m-1 and grid[i+1][j] == '1':
                        uf.union(flat(i,j), flat(i+1, j))
        return uf.count

优化

遍历时，若当前节点为1，使用后可以置0以减少重复计算

与130. 被围绕的区域不同，那里求并查集之后还需要用到’O‘的位置信息，因此使用后不能置’X‘