[LintCode] 433 Number of Islands 解题报告

Description
Given a boolean 2D matrix, 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.

Find the number of islands.


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.


思路
解法一
BFS
两重循环从所有有true的位置开始找。
从当前true的位置开始，BFS把所有相连的点找到，并把他们都设为false。这一轮找完以后我们把岛的个数加一。并且，这一坨因为都设成false了，以后就搜不到啦。


Code

public class Solution {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    class Point{
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    } 
     
    public int numIslands(boolean[][] grid) {
        // Write your code here
        if (grid == null || grid.length == 0 || grid[0] == null 
                                        || grid[0].length == 0) {
            return 0;
        }
        
        int n = grid.length;
        int m = grid[0].length;
        int island = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j]) {
                    bfs(grid, i, j);
                    island++;
                }
            }
        }
        
        return island;
    }
    
    public void bfs(boolean[][] grid, int x, int y) {

        Queue<Point> queue = new LinkedList<>();
        
        Point pt = new Point(x, y);
        queue.offer(pt);

        int[] goX = {-1, 1, 0, 0};
        int[] goY = {0, 0, -1, 1};
  
        while (!queue.isEmpty()) {
            Point curr = queue.poll();
            grid[curr.x][curr.y] = false;

            for (int i = 0; i < 4; i++) {
                Point adj = new Point(curr.x + goX[i], curr.y + goY[i]);
                if (inBound(adj, grid) && grid[adj.x][adj.y]) {
                    queue.offer(adj);
                }
            }
        }
    }
    
    public boolean inBound(Point pt, boolean[][] grid) {
        return pt.x >= 0 && pt.x < grid.length 
            && pt.y >= 0 && pt.y < grid[0].length;
    }
}

解法二
Union Find
Initialize的时候过一遍数组把1的总数记下，表示当前component的数量。
遍历数组，如果当前值是1，把周围是1的都给union上。注意我们只需要往右和往下走。因为左边和上面已经遍历过了。
每次union的时候，如果连上了，就把component的数字减一。最后搞完以后，component的数量就是岛的个数。

public class Solution {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    class UF{
        private int[] id;
        private int numComponent;
            
        public UF(boolean[][] grid) {
            numComponent = 0;
            int n = grid.length;
            int m = grid[0].length;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j]) {
                        numComponent++;
                    }
                }
            }
            id = new int[n * m];
            for (int i = 0; i < id.length; i++) {
                id[i] = i;
            }
        }
        
        public int find(int i) {
            while (i != id[i]) {
                id[i] = id[id[i]];
                i = id[i];
            }
            return i;
        }
            
        public void union(int p, int q) {
            int i = find(p);
            int j = find(q);
            if (i != j) {
                id[i] = j;
                numComponent--;
            }
        }
        
        public int getNumComponent() {
            return numComponent;
        } 
            
    }
        
    public int numIslands(boolean[][] grid) {
        // Write your code here
        
        if (grid == null || grid.length == 0 
            || grid[0] == null || grid[0].length == 0) {
            return 0;
        }
        
        int n = grid.length;
        int m = grid[0].length;
        UF uf = new UF(grid);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!grid[i][j]) {
                    continue;
                }
                int p = i * m + j;
                
                // connect right
                if (j + 1 < m && grid[i][j + 1]) {
                    int q = p + 1;
                    uf.union(p, q);
                }
                
                //connect down
                if (i + 1 < n && grid[i + 1][j]) {
                    int q = p + m;
                    uf.union(p, q);
                }
            }
        }
        
        return uf.getNumComponent();
    }
}