可视化图解算法56：岛屿数量

原创

用户11589437

发布于 2025-07-17 18:08:08

1390

文章被收录于专栏：数据结构与算法精讲数据结构与算法精讲

牛客网面试笔试 TOP101

1. 题目

描述

给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右）判断岛屿个数。

例如：

输入

[

[1,1,0,0,0],

[0,1,0,1,1],

[0,0,0,1,1],

[0,0,0,0,0],

[0,0,1,1,1]

]

对应的输出为3

(注：存储的01数据其实是字符'0','1')

示例1

输入：

[ 
  [1,1,0,0,0],
  [0,1,0,1,1],
  [0,0,0,1,1],
  [0,0,0,0,0],
  [0,0,1,1,1]
]

返回值：

示例2

输入：

[
  [0]
]

返回值：

示例3

输入：

[
  [1,1],
  [1,1]
]

返回值：

备注：

01矩阵范围<=200*200

2. 解题思路

岛屿数量的计算可以通过遍历+递归的形式完成，具体思路如下：

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

3. 编码实现

核心代码如下：

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 判断岛屿数量
 * @param grid char字符型二维数组
 * @return int整型
 */
func solve(grid [][]byte) int {
  // write code here
  count := 0 //岛屿个数
  //遍历二维数组的每一个元素 统计岛屿的个数
  for i := 0; i < len(grid); i++ {
    for j := 0; j < len(grid[0]); j++ {
      if grid[i][j] == '1' {
        //如果当前元素是1，岛屿的数量加1
        count++
        //递归处理岛屿（相邻的设置为0：因为该岛屿已经计算过）
        dfs(grid, i, j)
      }
    }
  }
  return count
}

// 把当前元素以及他邻近的为1的元素都置为0
func dfs(grid [][]byte, i int, j int) {
  // 2.递归终止条件：边界条件判断，不能越界; grid[i][j] == '0'：非岛屿，返回
  if (i < 0 || i >= len(grid)) || (j < 0 || j >= len(grid[0])) || (grid[i][j] == '0') {
    return
  }

  // 1. 递归步骤
  // 1.1 设置当前岛屿置位0（已经计算过）
  grid[i][j] = '0'
  // 1.2 对上、下、左、右 连着的4个方向进行递归处理（如果为岛屿，即 grid[i][j] == '1'，置0）
  dfs(grid, i-1, j) //上
  dfs(grid, i+1, j) //下
  dfs(grid, i, j-1) //左
  dfs(grid, i, j+1) //右
}

具体完整代码你可以参考下面视频的详细讲解。

4.小结

岛屿的计算方法为：遍历二维数组中的每一个元素，如果是1则岛屿计数，同时通过递归的方式将连接的岛屿（相邻元素为1值）设置为海洋（元素值设置为0，因为该岛屿已经计算过）。