Given a 2d grid map of'1's (land) and'0's (water), count the number of islands. 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 1:

11110


11010


11000


00000

Answer: 1

Example 2:

11000


11000


00100


00011

Answer: 3

tag: BFS, Union Find

class Solution {
    private class UnionFind{
        int[] father;
        int count;

        public UnionFind(int n, int m){
            father = new int[n * m];
            for (int i = 0; i < n * m; i++){
                father[i] = i;
            }
            count = 0;
        }

        public void add(){
            this.count++;
        }

        public int query(){
            return this.count;
        }

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

            return father[x] = find(father[x]);
        }

        public void union(int a, int b){
            int father_a = find(a);
            int father_b = find(b);

            if (father_a != father_b){
                father[father_a] = father_b;
                this.count--;
            }
        }
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int n = grid.length, m = grid[0].length;
        UnionFind uf = new UnionFind(n, m);

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (grid[i][j] == '1') uf.add();
            }
        }

        int[][] moves = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (grid[i][j] != '1') continue;
                for (int k = 0; k < 4; k++){
                    int xx = i + moves[k][0];
                    int yy = j + moves[k][1];

                    if (xx < 0 || xx >= n || yy < 0 || yy >= m || grid[xx][yy] != '1') continue;
                    uf.union(i * m + j, xx * m + yy);
                }
            }
        }

        return uf.query();
    }
}