Number of Islands

Source

• lintcode: Number of Islands

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

Note
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.

Java

public class Solution {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    public int numIslands(boolean[][] grid) {
        if(grid.length==0 || grid[0].length==0) return 0;
        int result=0;
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(!visited[i][j] && grid[i][j]==true){
                    dfs(grid ,i, j, visited);
                    result++;
                }
            }
        }
        return result;
    }

    public void dfs(boolean[][] grid, int m, int n, boolean[][] visited){
        if(m<0 || n<0 || m>grid.length-1 || n>grid[0].length-1){
            return;
        }
        if(visited[m][n] || grid[m][n]==false){
            return;
        }
        visited[m][n]=true;
        //top
        dfs(grid, m-1, n, visited);
        //bottom
        dfs(grid, m+1, n, visited);
        //left
        dfs(grid, m, n-1, visited);
        //right
        dfs(grid, m, n+1, visited);
    }
}