题目描述（中等难度）

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成
此外，你可以假设该网格的四条边均被水包围。
示例 1：

  1. 输入：grid = [
  2.   ["1","1","1","1","0"],
  3.   ["1","1","0","1","0"],
  4.   ["1","1","0","0","0"],
  5.   ["0","0","0","0","0"]
  6. ]
  7. 输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

解法一 拓展法(DFS)

思路:

想法很简单，我们只需要遍历二维数组，然后遇到 的时候，把当前的 以及它周围的所有 都标记成一个字符，这里直接标记成 。然后记录遇到了几次 ，就代表有几个岛屿
还有一个问题就是怎么标记与当前 相邻的 。也很直接，我们直接把和当前 连通的位置看做一个图，然后做一个遍历即可。可以直接用递归写一个 ，即深度优先遍历。DFS

public int numIslands(char[][] grid) {
        //判断该网格是否存在，不存在就是0个岛屿
        if (grid == null || grid.length == 0){
            return 0;
        }
        //初始化结果(岛屿)的数量
        int result = 0;
        int row = grid.length;
        int col = grid[0].length;
        //遍历每一个格子
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1'){
                    result++;
                    //寻找'1'(陆地),并且把'1'及其周围改为'0'
                    dfs(grid,i,j,row,col);
                }
            }
        }
        return result;
    }

    private void dfs(char[][] grid, int x, int y, int row, int col) {
        //如果超出边界或该格子是水域则跳出循环
        if (x<0 || y<0 || x>= row || y>= col || grid[x][y] == '0'){
            return;
        }
        //把该格子变为'0'(水域)
        grid[x][y] = '0';
        //向上下左右扩展
        dfs(grid, x-1, y, row, col);
        dfs(grid, x+1, y, row, col);
        dfs(grid, x, y-1, row, col);
        dfs(grid, x, y+1, row, col);
    }

解法二 BFS

思路:

当然做遍历的话，我们也可以采用，广度优先遍历。图的广度优先遍历和二叉树的层次遍历类似，只需要借助一个队列即可。BFS
和上边的区别不大，改一下标记函数即可。
此外入队列的时候，我们把二维坐标转为了一维，就省去了再创建一个类表示坐标。

public int numIslands2(char[][] grid) {
        if (grid == null || grid.length == 0){
            return 0;
        }
        int result = 0;
        int row = grid.length;
        int col = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1'){
                    result++;
                    queue.add(new int[]{i,j});
                    grid[i][j] = '0';
                    //while循环寻找这个'1'(陆地)周围的所有'1'
                    while (queue.size()>0){
                        int[] cur = queue.poll();
                        int x = cur[0];
                        int y = cur[1];
                        //>=0,是判断是否出界
                        if (x-1 >= 0 && grid[x-1][y] == '1'){
                            queue.add(new int[]{x-1,y});
                            grid[x-1][y] = '0';
                        }
                        if (y-1 >= 0 && grid[x][y-1]=='1'){
                            queue.add(new int[]{x,y-1});
                            grid[x][y-1]='0';
                        }
                        //注意这里是 < 不是<=
                        if(x+1 < row && grid[x+1][y] == '1'){
                            queue.add(new int[]{x+1,y});
                            grid[x+1][y] = '0';
                        }
                        if(y+1 < col && grid[x][y+1] == '1'){
                            queue.add(new int[]{x,y+1});
                            grid[x][y+1] = '0';
                        }
                    }
                }
            }
        }
        return  result;
    }