200. 岛屿数量（中等）

Blind 75 › 200. 岛屿数量（中等）（第 1 章）

题目

给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，统计其中“岛屿”的数量。岛屿由水平或竖直方向相邻的陆地连成一片；网格四条边界之外都视作水，所以贴边的陆地也不会延伸到网格外。

自造示例（按行看，1 是陆地、0 是水）：

grid = [
  ['1','1','0','0'],
  ['1','0','0','1'],
  ['0','0','0','1']
]

左上角 (0,0),(0,1),(1,0) 连成一座岛；右上角 (1,3),(2,3) 竖直相连成另一座岛，因此输出 2。

约束：m == grid.length、n == grid[i].length，且 1 ≤ m, n ≤ 300；grid[i][j] 只能是 '0' 或 '1'。

思路

一句话：这是一道“连通分量计数”题——从每块未访问的陆地出发，把和它连成一片的陆地一次性吞掉，每出发一次就 +1。

先想最直白的做法：把每个 '1' 看成一个点，上下左右相邻的两个 '1' 连一条边，然后数这张图里有几个连通块。直接枚举所有点对判断是否相邻，要 O((m·n)²)；更关键的是，如果“每遇到一个 1 就从它出发把整片数一遍”却不做标记，同一座岛会被重复计数很多次。

关键观察：一次搜索就能把一整座岛“吃干净”。从任意一块陆地出发，沿着上下左右一直走，凡是能走到的陆地都属于同一座岛；只要在走过时立刻标记，后面再遇到它们就跳过，这样每座岛只会被数一次。

做法有 DFS、BFS、并查集三种，结果相同。这里用 DFS：递归实现最直观；把访问过的陆地直接改成 '0' 还能省掉额外的 visited 数组。

解法

主流程两重循环扫全图，DFS 负责吞并一座岛：

遇到 '1'：岛屿数 + 1，从该格子开始 DFS。
DFS 进入格子后，先判越界 / 是否已经是水，是则返回。
把当前格子改成 '0'（既表示访问过，又表示已从陆地中移除）。
递归尝试上、下、左、右四个邻居。
扫描结束，返回累计的岛屿数。

扫描到	动作	吞掉的格子	岛屿数
(0,0)=1	+1 后 DFS	(0,0),(0,1),(1,0)	1
(0,1)=0	跳过	—	1
(1,0)=0	跳过	—	1
(1,3)=1	+1 后 DFS	(1,3),(2,3)	2
(2,3)=0	跳过	—	2

被吞掉的格子已变成 '0'，因此后续扫描不会再触发计数。

下图把上面 5 个步骤串成流程，并逐步演示：

200. 岛屿数量（中等）解法步骤流程图 — 图① 解法步骤流程图（共 5 步）。

200. 岛屿数量（中等）按步骤逐步执行的动画 — 动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →

class Solution {
public:
 int numIslands(vector<vector<char>>& grid) {
 int rows = grid.size();
 int cols = grid[0].size();
 int islands = 0;  for (int r = 0; r < rows; ++r) {
 for (int c = 0; c < cols; ++c) {
 if (grid[r][c] == '1') {
 ++islands;
 dfs(grid, r, c, rows, cols);
 }
 }
 }
 return islands;
 }  private:
 void dfs(vector<vector<char>>& grid, int r, int c, int rows, int cols) {
 if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0') {
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。

一木科技

一木科技