题目

描述

• 给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
  岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。

方法一

思路

• 1.题目要求找出所有的值为1的块，所以需要遍历搜索整个二维数组；
• 2.首先找到一个值为1的节点，然后通过DFS遍历搜索找出与之相同的所有值为1的节点，并全都置为0，以免干扰后面的搜索；并将岛屿数加一；
• 3.重复2的步骤，直至遍历完整个数组。

具体步骤

• 见下图：
  
  
  

• 具体代码：

  import java.util.*;
  public class Solution {
  /**
   * 判断岛屿数量
   * @param grid char字符型二维数组 
   * @return int整型
   */
  public int solve (char[][] grid) {
      // write code here
      if (grid == null || grid.length == 0) {
          return 0;
      }
      int islandNums = 0;
      // 遍历整个二维数组
      for (int row = 0; row < grid.length; ++row) {
          for (int col = 0; col < grid[0].length; ++col) {
              // 找到岛屿
              if (grid[row][col] == '1' ) {
                  islandNums++;
                  search(grid, row, col);
              }
          }
      }
      return islandNums;
  }
  private void search(char[][] grid,int row,int col){
      // 越过边界，0 直接返回
      if (row < 0 || row >= grid.length || col < 0 ||
          col >= grid[0].length || grid[row][col] == '0'){
          return ;
      }
      // 已找到，置为'0'，以免干扰后面岛屿的遍历
      grid[row][col] = '0';
      // DFS查找与之相连的节点，全都置为'0'
      search(grid, row, col - 1);
      search(grid, row, col + 1);
      search(grid, row - 1, col);
      search(grid, row + 1, col);
  }
  }

• 时间复杂度：,遍历整个二维数组；

• 空间复杂度：,递归遍历整个二维数组，整个网格均为陆地，需要m*n。

方法二

思路

• 方法一使用的是DFS，那么同样可以使用BFS进行遍历找出所有想通的节点，只不过DFS可以通过系统实现栈的存储，而BFS则需要通过队列实现。

具体步骤

• 由于整体思路与方法一相同，所以就不再具体介绍了。

• 代码如下：

  import java.util.*;
  public class Solution {
  // 节点类
  class Point{
     int x,y;
     public Point(int x,int y){
         this.x = x;
         this.y = y;
     }
  }
  /**
  * 判断岛屿数量
  * @param grid char字符型二维数组 
  * @return int整型
  */
  public int solve (char[][] grid) {
     // 岛屿数量
     int islandNums = 0;   
     // 队列，辅助bfs遍历
     LinkedList<Point> points = new LinkedList<>();
     for(int i = 0; i < grid.length; ++i) {
         for(int j = 0; j < grid[0].length; ++j) {
             // 找到一个没走过的岛屿起始点
             if(grid[i][j] == '1' ) {
                 points.add(new Point(i, j));
                 grid[i][j] = '0';
                 islandNums++;
                 while(!points.isEmpty()) {
                     Point t = points.pollFirst();
                     int x = t.x;
                     int y = t.y;
                     // 四周的点加入队列
                     if(x - 1 >= 0 && grid[x - 1][y] == '1') {
                         points.add(new Point(x - 1, y));
                         grid[x-1][y] = '0';
                     }
                     if(x + 1 < grid.length && grid[x + 1][y] == '1') {
                         points.add(new Point(x + 1, y));
                         grid[x+1][y] = '0';
                     }
                     if(y - 1 >= 0 && grid[x][y - 1] == '1') {
                         points.add(new Point(x, y - 1));
                         grid[x][y-1] = '0';
                     }
                     if(y + 1 <grid[0].length && grid[x][y + 1] == '1') {
                         points.add(new Point(x, y + 1));
                         grid[x][y+1] = '0';
                     }
                 }
             }
         }
     }
     return islandNums;
  }
  }

• 时间复杂度：,遍历整个二维数组；

• 空间复杂度：，使用了队列来辅助BFS运算，所以最坏为。