Number of Islands

如何把二维坐标(x,y) 转化为一维的Union Find,

• id = x*m + y
• x = id / m
• y = id % m

具体到这道题，从每个点出发，检查其周围的点是否为陆地能够与之相连。

class Solution {
    class UnionFind {
        int count;
        int[] father;
        public UnionFind(int n) {
            father = new int[n];
            //因为有0点了，所以必须指向自己
            for (int i = 0; i < n; ++i) {
                father[i] = i;
            }
        }

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

        private void connect(int a, int b) {
            int root_a = find(a);
            int root_b = find(b);
            if (root_a != root_b) {
                father[root_a] = root_b;
                count--;
            }
        }

        private void setCount(int count) {
            this.count = count;
        }

        private int query() {
            return count;
        }
    }

    public int numIslands(char[][] grid) {
        int count = 0;
        int n = grid.length;
        if (n == 0) return 0;
        int m = grid[0].length;
        if (m == 0) return 0;
        UnionFind union_find = new UnionFind(n * m);

        //get count
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1')
                    count++;
            }
        }
        union_find.setCount(count);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    if (i > 0 && grid[i-1][j] == '1') 
                        union_find.connect(i*m+j, (i-1)*m+j);

                    if (i < n-1 && grid[i+1][j] == '1')
                        union_find.connect(i*m+j, (i+1)*m+j);

                    if (j > 0 && grid[i][j-1] == '1')
                        union_find.connect(i*m+j, i*m+j-1);

                    if (j < m-1 && grid[i][j+1] == '1')
                        union_find.connect(i*m+j, i*m+j+1);
                }
            }
        }

        return union_find.query();
    }
}