4.岛屿数量

题目

给你一个由'1'(陆地)和'0'(水)组成的二维网格，请你计算网格中的岛屿数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

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

思路

首先，我们要在二维矩阵中找到第一个'1'出现的位置，这一步是毫无疑问的。那我们如何找到水平方向和竖直方向上是否有连接的陆地，并且统计岛屿数量呢？

比如我们找到第一个'1'出现的位置后，可以向左搜索，看看为不为'1'，再回到原位，向右搜索，看看为不为'1'......这不就是DFS的算法吗，"不到黄河不回头"，可劲搜，直到走到头再回来继续朝另一个方向搜，发现为'0'，就跳出搜索。

那知道怎么搜之后，岛屿数量是多少呢？下次搜如何避免重复统计呢？

在dfs搜索之前，一旦遍历到一个'1'，就统计+1，因为dfs不论有没有搜到'1'，有没有连接多个'1'变成一个岛屿，最后都是一个岛屿，只不过是岛屿的大小而已。

不难写出以下代码。

public int findOnes(char[][] grid){
  int res = 0;
  for(int i = 0;i < grid.length;i++){
    for(int j = 0;j < grid[0].length;j++){
      if(grid[i][j] == '1'){
        res++;
        dfs(i,j,grid);
      }
    }
  }
  return res;
}

private void dfs(int i,int j,char[][] grid){
  // 跳出搜索条件，注意边界条件
  if(i < 0 || i > grid.length-1 || j < 0 || j > grid[0].length-1 || grid[i][j] == '0'){
    return;
  }
  grid[i][j] = '0';
  dfs(i+1,j,grid);
  dfs(i-1,j,grid);
  dfs(i,j+1,grid);
  dfs(i,j-1,grid);
}