Given a 2d grid map of'1's (land) and'0's (water), count 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

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]
]

return3.

思路：如何理解连片的1，其实就是对于特定的坐标[x,y]=1, 连接此坐标的临近四个坐标是否存在1，所以就变成一个搜索问题。

解法1：DFS

 grid\\[i\\]\\[j\\] = 1;》》》》》》check           dfs\\(grid,i-1,j\\);dfs\\(grid,i+1,j\\);dfs\\(grid,i,j-1\\);dfs\\(grid,i,j+1\\);

因为连片的1只能算一次有效count， 所以一旦搜索到临近的1，set it = 0。

public class Solution {


    private int m, n;
    public void dfs(boolean[][] grid, int i, int j) {
        if(i < 0 || i >= m || j < 0 || j >= n){
            return;
        }

        if(grid[i][j]){
            grid[i][j] = false;
            dfs(grid,i-1,j);
            dfs(grid,i+1,j);
            dfs(grid,i,j-1);
            dfs(grid,i,j+1);
        }

    }

    public int numIslands(boolean[][] grid) {
        m = grid.length;
        if(m == 0){
            return 0;
        }
        n = grid[0].length;
        if( n == 0){
            return 0;
        }

        int ans = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(!grid[i][j]){
                    continue;
                }
                ans++;
                dfs(grid,i,j);
            }
        }

        return ans;
    }
}