企业官网建设流程全解析

本文概览：本文以LeetCode题目"岛屿数量"为例，从二叉树的递归视角迁移到二维网格的四方向递归，讲解DFS和BFS两种标记岛屿的方法

一、题目

二、题目分析

题目要求：给定一个二维网格，计算岛屿的数量。‘1’ 代表陆地，‘0’ 代表水

什么是岛屿？这是这题最容易让人困惑的地方。岛屿的定义是：对于某个 ‘1’，它的上下左右如果也是 ‘1’，就属于同一个岛屿。但如果斜着的 ‘1’，则不属于这个岛屿的一部分

看下面这个例子：

1 1 0 1 0 1

• 左上角的三个 1：左上和右上是横向相邻（连通），左上和左下是纵向相邻（连通），所以这三个 1 属于同一个岛屿
• 右下角的 1：和左下的 1 是斜着相邻，但斜方向不算连通，所以它是一个独立的岛屿

最终这个网格有 2 个岛屿。关键就是：只有上下左右方向相邻的 1 才算连通，斜方向不算

理解了岛屿的定义后，这题其实和前面做过的二叉树是同一个套路：

二叉树从父节点往子节点走，天然不会走回去。但二维网格四个方向走来走去，会重复访问同一个格子，所以必须标记已访问的格子

整体思路：遍历整个网格，每遇到一个新的 ‘1’，就代表发现了一个新岛屿，count+1，然后把这个岛屿的所有陆地都标记掉（变成 ‘0’），以后再遍历到就不算了。标记的方法有两种：DFS 和 BFS

思路概览

方法一：DFS

classSolution{// 岛屿数量privateintcount=0;// 上下左右privatefinalint[][]dirs={{1,0},{-1,0},{0,-1},{0,1}};// 长宽privateintrows,cols;publicintnumIslands(char[][]grid){if(grid==null||grid.length==0){return0;}rows=grid.length;cols=grid[0].length;for(inti=0;i<rows;i++){for(intj=0;j<cols;j++){if(grid[i][j]=='1'){dfs(grid,i,j);count++;}}}returncount;}privatevoiddfs(char[][]grid,inti,intj){if(i<0||i>=rows||j<0||j>=cols||grid[i][j]=='0'){return;}// 标记为已访问过grid[i][j]='0';// 递归访问上下左右for(int[]dir:dirs){intnewRow=i+dir[0];intnewCol=j+dir[1];dfs(grid,newRow,newCol);}}}

方法二：BFS

classSolution{// 岛屿数量privateintcount=0;// 上下左右privatefinalint[][]dirs={{1,0},{-1,0},{0,-1},{0,1}};// 长宽privateintrows,cols;publicintnumIslands(char[][]grid){if(grid==null||grid.length==0){return0;}rows=grid.length;cols=grid[0].length;for(inti=0;i<rows;i++){for(intj=0;j<cols;j++){if(grid[i][j]=='1'){bfs(grid,i,j);count++;}}}returncount;}privatevoidbfs(char[][]grid,inti,intj){Queue<int[]>queue=newLinkedList<>();// 入队时就标记，防止重复加入grid[i][j]='0';queue.offer(newint[]{i,j});while(!queue.isEmpty()){int[]cur=queue.poll();introw=cur[0];intcol=cur[1];// 遍历上下左右for(int[]dir:dirs){intnewRow=row+dir[0];intnewCol=col+dir[1];if(newRow>=0&&newRow<rows&&newCol>=0&&newCol<cols&&grid[newRow][newCol]=='1'){// 入队时就标记为已访问grid[newRow][newCol]='0';queue.offer(newint[]{newRow,newCol});}}}}}

思路简要说明

建议DFS和BFS都掌握，这是入门图类型算法题的好题目

两种方法的外层逻辑完全一样：遍历网格，遇到 ‘1’ 就 count+1 并把整个岛屿标记掉。区别只在标记岛屿的方式：

1. DFS：遇到 ‘1’，递归它的上下左右，一路走到头，和二叉树的先序遍历一个道理
2. BFS：遇到 ‘1’，把它周围的 ‘1’ 全部加入队列，一层层往外扩散
3. BFS 的关键细节：标记时机必须是入队时，不是出队时。如果出队才标记，同一个格子会被重复加入队列，导致死循环

三、思路详解

第一步：从二叉树到二维网格

前面做了很多二叉树的题目，核心就是从一个节点出发，递归访问它的左右子树。这题其实是一样的思路，只是方向从 2 个变成了 4 个：

二叉树（2个方向）： 二维网格（4个方向）： 节点 上 / \ | 左 右 左 — (i,j) — 右 | 下

二叉树的递归模板：

privatevoiddfs(TreeNodenode){if(node==null)return;// 出口// 处理当前节点dfs(node.left);// 递归左dfs(node.right);// 递归右}

二维网格的递归模板：

privatevoiddfs(char[][]grid,inti,intj){if(越界||grid[i][j]=='0')return;// 出口grid[i][j]='0';// 标记已访问// 递归上下左右for(int[]dir:dirs){dfs(grid,i+dir[0],j+dir[1]);}}

结构完全一样，区别只有两点：出口条件多了"越界判断"，以及递归前多了一步"标记已访问"

第二步：为什么需要标记？

二叉树从父节点往子节点走，是单向的，天然不会走回去。但二维网格四个方向是互相的——你从 (0,0) 走到 (0,1)，(0,1) 的左边方向又指回 (0,0)，如果不标记就会无限来回走

不标记的情况： (0,0) → 访问右边 (0,1) (0,1) → 访问左边 (0,0) ← 又回去了！ (0,0) → 访问右边 (0,1) ← 又回来了！ ... 死循环

所以每次访问一个格子，必须立刻把它变成 ‘0’，这样后续任何方向走到这里都会直接 return

第三步：DFS 标记过程图解

以这个 4×5 网格为例：

1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1

遍历到 (0,0)，发现 ‘1’，count=1，开始 DFS 标记

① 访问 (0,0)，标记为 '0'，递归上下左右 [0] 1 0 0 0 ← (0,0) 标记 1 1 0 0 0 ② 上越界，下到 (1,0)，标记为 '0' [0] 1 0 0 0 [0] 1 0 0 0 ← (1,0) 标记 ③ (1,0) 的下越界，左越界，右到 (1,1)，标记为 '0' 0 1 0 0 0 [0][0]0 0 0 ← (1,1) 标记 ④ (1,1) 的上是 (0,1)，标记为 '0' [0][0]0 0 0 ← (0,1) 标记 0 [0]0 0 0 ⑤ (0,1) 的上下左右要么越界要么是 '0'，递归结束 标记后的网格： 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1

继续遍历到 (2,2)，发现 ‘1’，count=2，DFS 标记它（单个格子）

继续遍历到 (3,3)，发现 ‘1’，count=3，DFS 标记 (3,3) 和 (3,4)

最终 count = 3

第四步：BFS 标记过程图解

BFS 的思路不是一路走到头，而是一层层往外扩散。以 (0,0) 为例：

初始： [1] 1 0 0 0 ← (0,0) 入队并标记为 '0' 1 1 0 0 0 第一轮：出队 (0,0)，把周围的 '1' 入队并标记 [0][1]0 0 0 ← (0,1) 入队标记 [1] 1 0 0 0 ← (1,0) 入队标记 队列：[(0,1), (1,0)] 第二轮：出队 (0,1)，周围没有未标记的 '1' 出队 (1,0)，把 (1,1) 入队并标记 0 [0]0 0 0 [0][1]0 0 0 ← (1,1) 入队标记 队列：[(1,1)] 第三轮：出队 (1,1)，周围没有未标记的 '1' 队列为空，BFS 结束

第五步：BFS 的关键细节——入队时标记还是出队时标记？

这是 BFS 写法里最容易踩坑的地方

错误写法（出队时标记）：

// ❌ 错误：出队时才标记while(!queue.isEmpty()){int[]cur=queue.poll();grid[cur[0]][cur[1]]='0';// 出队才标记for(int[]dir:dirs){intnewRow=cur[0]+dir[0];intnewCol=cur[1]+dir[1];if(越界判断&&grid[newRow][newCol]=='1'){queue.offer(newint[]{newRow,newCol});// 没有标记！}}}

为什么错？看这个例子：

初始：queue = [(0,0)]，grid[0][0] 还是 '1' 第一轮：出队 (0,0)，标记为 '0' 检查周围，发现 (0,1) 和 (1,0) 是 '1'，加入队列 queue = [(0,1), (1,0)] 第二轮：出队 (0,1)，标记为 '0' 检查周围，发现 (1,1) 是 '1'，加入队列 同时 (0,0) 已经是 '0' 了，跳过 queue = [(1,0), (1,1)] 第三轮：出队 (1,0)，标记为 '0' 检查周围，(0,0) 是 '0' 跳过 但 (1,1) 还是 '1'！（还没出队，没被标记） 于是又把 (1,1) 加入队列！ queue = [(1,1), (1,1)] ← 重复了！

同一个格子被加入队列多次，每个出队时又会把周围的 ‘1’ 加入队列，最终导致死循环

正确写法（入队时标记）：

// ✅ 正确：入队时就标记grid[newRow][newCol]='0';// 入队前立刻标记queue.offer(newint[]{newRow,newCol});

入队时就标记成 ‘0’，后面其他格子检查到它时看到的是 ‘0’，就不会重复加入了。一个格子只会入队一次，不会死循环

第六步：DFS vs BFS 对比

两种方法只是标记岛屿的遍历方式不同，最终都能把同一个岛屿的所有陆地标记掉，不影响 count 的计算

复杂度分析

• 时间复杂度：O(rows×cols)，每个格子最多被访问一次
• 空间复杂度：O(rows×cols)，DFS 最坏递归深度，BFS 最坏队列长度