Number of Islands

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

Have you met this question in a real interview? 

Yes

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.

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 count = 0;

        for(int i = 0; i < grid.length; i++){

            for(int j = 0; j < grid[0].length; j++){

                if(grid[i][j] == true){

                    count++;

                    remove(grid, i, j);

                }

            }

        }

        return count;

    }

    

    private void remove(boolean[][] grid, int row, int col){

        if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || !grid[row][col]) return;

        grid[row][col] = false;

        remove(grid, row+1, col);

        remove(grid, row-1, col);

        remove(grid, row, col-1);

        remove(grid, row, col+1);

        

    }

}