lintcode433- Number of Islands- easy

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。灌水法。BFS做的事是把当前点开始出去的连通点都变为0(和前面那题写法差不多)。main里面做的事是遍历所有点，碰到1就计数cnt++，然后调用bfs把当前块变0不影响后面的遍历。最后cnt就是答案。

public class Solution {
    /*
     * @param grid: a boolean 2D matrix
     * @return: an integer
     */
    public int numIslands(boolean[][] grid) {
        // write your code here
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        
        int h = grid.length;
        int w = grid[0].length;
        int cnt = 0;
        for (int x = 0; x < w; x++) {
            for (int y = 0; y < h; y++) {
                if (grid[y][x]) {
                    cnt++;
                    bfs(grid, x, y);
                }
            }
        }
        return cnt;
        
    }
    
    private void bfs (boolean[][] grid, int x, int y) {
        
        grid[y][x] = false;
        int[] dx = {0, -1, 0, 1};
        int[] dy = {-1, 0, 1, 0};
        int h = grid.length;
        int w = grid[0].length;
        
        for (int i = 0; i < 4; i++) {
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (cx >= 0 && cx < w && cy >= 0 && cy < h && grid[cy][cx]) {
                bfs(grid, cx, cy);
            }
        }
    }
}