Number of Islands 2

题目地址：
https://leetcode.com/problems/number-of-islands-ii/#/description

题目：

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

We return the result as an array: [1, 1, 2, 3]

解题思路：
这道题需要用一个roots的array来做union，长度是m*n。拿到一个point，首先把count+1， 然后朝四个方向延伸一个，如果越界或者为-1，那么continue；如果不是，那通过roots和mappedIndex首先找到mappedRoot，如果root和mappedRoot不一样，那么将roots[root] 设为 mappedRoot，将root设为mappedRoot，然后将count--。



代码：

private int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

public List<Integer> numIslands2(int m, int n, int[][] positions) {
    List<Integer> rst = new ArrayList<>();
    if(m == 0 || n == 0 || positions == null || positions.length == 0 || positions[0].length == 0){
        return rst;
    }
    int[] check = new int[m * n];
    Arrays.fill(check, -1);
    for(int i = 0; i <= positions.length - 1; i++){
        int curr = rst.size() == 0 ? 0 : rst.get(rst.size() - 1);
        int temp = tryToFill(check, curr, m, n, positions[i][0], positions[i][1]);
        rst.add(temp);
    }
    return rst;
}

private int tryToFill(int[] check, int prev, int m, int n, int i, int j) {
    int root = i * n + j;
    if(check[root] != -1){
        return prev;
    }
    prev++;
    // here very important    check[root] = root;
    for(int[] dir : dirs){
        int x = i + dir[0];
        int y = j + dir[1];
        int index = x * n + y;
        if(x < 0 || y < 0 || x >= m || y >= n || check[index] == -1){
            continue;
        }
        // find the mappedRoot that my curr root could map to        int mappedRoot = unionFind(check, index);
        // if this node connect two island(with different root)        if(root != mappedRoot){
            check[root] = mappedRoot;
            root = mappedRoot;
            prev--;
        }
    }
    return prev;
}

private int unionFind(int[] roots, int mappedIndex) {
    while(mappedIndex != roots[mappedIndex]){
        mappedIndex = roots[mappedIndex];
    }
    return mappedIndex;
}