岛屿的个数II

https://www.lintcode.com/problem/434/?utm_source=sc-libao-ql

描述

给定 n, m, 分别代表一个二维矩阵的行数和列数, 并给定一个大小为 k 的二元数组A. 初始二维矩阵全0. 二元数组A内的k个元素代表k次操作, 设第i个元素为 (A[i].x, A[i].y), 表示把二维矩阵中下标为A[i].x行A[i].y列的元素由海洋变为岛屿. 问在每次操作之后, 二维矩阵中岛屿的数量. 你需要返回一个大小为k的数组.

设定0表示海洋, 1代表岛屿, 并且上下左右相邻的1为同一个岛屿.

样例

样例 1:

输入: n = 4, m = 5, A = [[1,1],[0,1],[3,3],[3,4]]输出: [1,1,2,2]解释: 0.  00000    00000    00000    000001.  00000    01000    00000    000002.  01000    01000    00000    000003.  01000    01000    00000    000104.  01000    01000    00000    00011

样例 2:

输入: n = 3, m = 3, A = [[0,0],[0,1],[2,2],[2,1]]输出: [1,1,2,2]

解题思路：

用union find，每次操作都寻找周围4点，如果周围点是岛（坐标是1），就尝试联通。

注意：

1 Union 所有操作仅对父节点，并且只有父节点不一样时候才union。 P用index而非直接（x,y)

2 rank是树的高度， 为了优化空间和时间

3 此处count 从0开始 不是n

4 注意4个方向的遍历模板

```python
from typing import (
    List,
)
from lintcode import (
    Point,
)

"""
Definition for a point:
class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y
"""
class UnionFind:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.count = 0
        self.rank = [1]*n
    
    def find(self, p):
        if self.father[p] != p:
            self.father[p] = self.find(self.father[p])
        return self.father[p]
    
    def union(self, p, q):
        fp = self.find(p)
        fq = self.find(q)
        if fp!= fq: #如果已经在同一岛， 不要count--
            if self.rank[fp] > self.rank[fq]:
                self.father[fq] = fp
            elif self.rank[fq] > self.rank[fp]:
                self.father[fp] = fq
            else:
                self.father[fp] = fq
                self.rank[fq] += 1
            self.count -= 1
    
    def getCount(self):
        return self.count
    
    def addIsland(self):
        self.count += 1


class Solution:
    """
    @param n: An integer
    @param m: An integer
    @param operators: an array of point
    @return: an integer array
    """
    def num_islands2(self, n: int, m: int, operators: List[Point]) -> List[int]:
        # write your code here
        res = []
        if not operators:
            return res
        uf = UnionFind(m*n)
        grid = [[0]*m for _ in range(n)]
        directions = [(1,0),(0,1),(-1,0),(0,-1)]
        for p in operators:
            x,y = p.x, p.y
            if grid[x][y] == 1: #减枝 如果已经连过 无需再连
                res.append(uf.getCount())
                continue
            index = x*m + y
            uf.addIsland()
            grid[x][y] = 1

            for dx,dy in directions:
                nx,ny = x+dx,y+dy
                if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:
                    uf.union(index, nx*m+ny)
            
            res.append(uf.getCount())
        
        return res


```