/**
1. 方格染色, 首先遍历所有点, 当grid[i][j] == '1' 时, 染色为'2', 并向4个方向递归染色, 染色次数就是岛屿个数
*/

/**
1. 并查集: 每遍历一个点就合并4个方向的所有相同点, 合并后将并查集所有子节点汇聚到根, 对根去重后统计为1的根的个数
*/


class Solution {

    class UnionFindSet{
        int n, block;
        int[] pre;
        public UnionFindSet(int n){
            this.pre = new int[n];
            this.n = n;
            this.block = n;
            for (int i = 0 ; i < n ; i++) this.pre[i] = i;
        }

        public int find(int x){
            if (x != pre[x]) 
                pre[x] = find(pre[x]);
            return pre[x];
        }

        public boolean union(int x, int y){
            int fx = find(x);
            int fy = find(y);
            if (fx == fy) return false;
            pre[fx] = fy;
            block --;
            return true;
        }
    }

    static final int[] dx = {0, 0, 1, -1};
    static final int[] dy = {1, -1 ,0, 0};

    public int numIslands(char[][] grid) {
        // return color(grid);
        return merge(grid);
    }

    public int merge(char[][] grid){
        if (grid == null || grid.length == 0) return 0;
        int n = grid.length;
        int m = grid[0].length;
        UnionFindSet ufs = new UnionFindSet(n*m);
        for (int i = 0 ; i < n ; i++){
            for (int j = 0 ; j < m ; j++){
                for (int k = 0 ; k < 4 ; k ++){
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if (0 <= x && x < n && 0 <= y && y < m && grid[x][y] == grid[i][j]) {
                        ufs.union(i*m+j, x*m+y);
                    }
                }
            }
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0 ; i < ufs.n; i ++) ufs.find(i);
        for (int i = 0 ; i < ufs.n; i ++) set.add(ufs.pre[i]);
        int count = 0;
        for (Integer i : set){
            int x = i / m;
            int y = i % m;
            count += grid[x][y] == '1' ? 1 : 0;
        }
        return count;
    }

    public int color(char[][] grid){
        if (grid == null || grid.length == 0) return 0;
        int n = grid.length;
        int m = grid[0].length;
        int count = 0;
        for (int i = 0; i < n ; i ++){
            for (int j = 0 ; j < m ; j ++){
                if (grid[i][j] == '1'){
                    count ++;
                    dfs(grid, i, j, n, m);
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j, int n, int m){
        grid[i][j] = '2';
        for (int k = 0; k < 4; k++){
            int x = i + dx[k];
            int y = j + dy[k];
            if (0 <= x && x < n && 0 <= y && y < m && grid[x][y] == '1')
                dfs(grid, x, y, n, m);
        }
    }
}