Number of Islands 433

Question

Given a boolean 2D matrix, find the number of islands.

Notice

0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Example

Given graph:

[

[1, 1, 0, 0, 0],

[0, 1, 0, 0, 1],

[0, 0, 0, 1, 1],

[0, 0, 0, 0, 0],

[0, 0, 0, 0, 1]

]

return 3.

Solution

这道题和Graph Valid Tree 178一样，既能用UF也能用dfs／bfs来寻找联通分量。

代码如下：

UF:

public class Solution {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    //uf模版
    class UnionFind{
        HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
        public UnionFind(int[] array){
            for(int i = 0; i < array.length; i++){
                father.put(i, i);
            }
        }

        public int compressed_find(int x){
            int parent = father.get(x);
            while(parent != father.get(parent)){
                parent = father.get(parent);
            }

            int temp = 0;
            int fa = x;
            while(fa != father.get(fa)){
                temp = father.get(fa);
                father.put(fa, parent);
                fa = temp;
            }

            return parent;
        }

        public void union(int a, int b){
            int aFather = compressed_find(a);
            int bFather = compressed_find(b);
            // if(aFather != bFather){
            //     father.put(aFather, bFather);
            // }
            father.put(aFather, bFather);
        }
    }

    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    public int numIslands(boolean[][] grid) {
        // Write your code here
        if(grid == null || grid.length == 0 || grid[0].length == 0){
            return 0;
        }

        int n = grid.length;
        int m = grid[0].length;
        int[] grid1D = new int[n * m];
        int count = 0;

        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                int index = i * m + j;
                if(grid[i][j] == true){
                    grid1D[index] = 1;
                    count++;
                }else{
                    grid1D[index] = 0;
                }
            }
        }

        UnionFind uf = new UnionFind(grid1D);

        for(int i = 0; i < grid1D.length; i++){
            if(grid1D[i] == 0){
                continue;
            }

            for(int j = 0; j < 4; j++){
                int indexX = i / m + dx[j];
                int indexY = i % m + dy[j];
                int index = indexX * m + indexY;
                if(indexX >= 0 && indexX < n && indexY >= 0 && indexY < m && grid1D[i] == grid1D[index]){
                    if(uf.compressed_find(i) != uf.compressed_find(index)){
                        uf.union(i, index);
                        count--;
                    }
                }
            }
        }

        return count;
    }
}

DFS:

public class Solution {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    private int m, n;
    public void dfs(boolean[][] grid, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n) return;

        if (grid[i][j]) {
            grid[i][j] = false;
            dfs(grid, i - 1, j);
            dfs(grid, i + 1, j);
            dfs(grid, i, j - 1);
            dfs(grid, i, j + 1);
        }
    }

    public int numIslands(boolean[][] grid) {
        // Write your code here
        m = grid.length;
        if (m == 0) return 0;
        n = grid[0].length;
        if (n == 0) return 0;

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!grid[i][j]) continue;
                ans++;
                dfs(grid, i, j);
            }
        }
        return ans;
    }
}