Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

<解題>

1. 用i,j表示行列，用迴圈去找如果[i][j]==1，就用conut+1，代表找到一個島，並callBFS看看是否周圍也有地(1)連接
2. callBFS中，把當前的1翻成0，並找他前後左右：if(i <0 || i>=grid.length || j<0 || j>=grid[i].length || grid[i][j] ==‘0’) return，代表已經沒有連續的1了

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i =0 ; i<grid.length; i++){
            for(int j = 0 ; j<grid[i].length ; j++){
                if(grid[i][j]=='1'){
                count +=1 ;
                callBFS(grid, i,j);
                }
            }
        }
        return count;
    }

    public void callBFS(char[][]grid, int i, int j){
        if(i <0 || i>=grid.length || j<0 || j>=grid[i].length || grid[i][j] =='0') return;
        grid[i][j] = '0';
        callBFS(grid, i+1 , j);//up
        callBFS(grid, i-1 , j);//down
        callBFS(grid, i , j+1);//right
        callBFS(grid, i , j-1);//left
    }
}

Time: O() Space: O()