题目

描述

给一个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);
}
}

时间复杂度： $O(mn)$ ,遍历整个二维数组；
空间复杂度： $O(mn)$ ,递归遍历整个二维数组，整个网格均为陆地，需要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;
}
}

时间复杂度： $O(mn)$ ,遍历整个二维数组；
空间复杂度： $O(mn)$ ，使用了队列来辅助BFS运算，所以最坏为 $O(mn)$ 。

题解 | #岛屿数量#

题目

描述

方法一

思路

具体步骤

方法二

思路

具体步骤