小探险家学算法

Appearance

27. 迷宫寻宝（图与 DFS） ​

知识点：深度优先搜索（DFS）—— 一条路走到黑，走不动再回头；连通区域计数

项目：数一数地图上有几座岛

故事开场：地图上有几座岛？ ​

老师拿来一张"小岛地图"，每个格子要么是陆地（1），要么是海水（0）：

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

"数一数，有几座岛？"老师问。

"一座岛 = 连在一起的陆地（上下左右相连）。"你数了数： "左上角 4 块连一起，是一座；中间 1 块，一座；右下角 2 块， 一座。一共 3 座！"

"对！"老师说，"那这张呢？"——老师把地图改成了 1000 × 1000 格， 密密麻麻全是陆地和海水。

你傻眼了："这……一块一块数，数到下一块陆地时，怎么知道它 是不是刚才那座岛的一部分？"

笨办法先行：数来数去，一座岛数了三遍 ​

你试着"遇到 1 就计数"：

ts
const map = [
  [1, 1, 0, 0, 0],
  [1, 1, 0, 0, 0],
  [0, 0, 1, 0, 0],
  [0, 0, 0, 1, 1],
]

let count = 0
for (let x = 0; x < map.length; x++) {
  for (let y = 0; y < map[x].length; y++) {
    if (map[x][y] === 1) {
      count++          // 看到陆地就 +1？
    }
  }
}
console.log("岛的数量：" + count)

输出：

岛的数量：8

8 座！ 可正确答案明明是 3 座——因为左上角那 4 块连在一起的陆地， 被数了 4 次！一块陆地计一次数，一座岛被数了"它的面积"那么多次。

"要是每座岛只数一次就好了……"你自言自语，"看到一块陆地， 把它整座岛都逛一遍、做个记号，下次再遇到记号就知道 '这座岛数过了'——那不就只数一次了吗？"

"逛遍整座岛"——这就是深度优先搜索（DFS）的活儿！

引出知识点：DFS——一条路走到黑 ​

深度优先搜索（Depth-First Search，简称 DFS），就是"探险家"式的走法：

认准一个方向，一直往前走；走不动了，退回来换一个方向。

第 23 章的迷宫（回溯）就是 DFS！它的规律：

  • 从起点出发
  • 能走就走（往一个方向走到黑）
  • 走不动了退回来（回溯）
  • 走过的路做记号，绝不重复走

在"数岛"这个问题里，DFS 的用处是淹没整座岛：

  1. 找到一块陆地（1）
  2. 从它开始 DFS：把这块陆地变成海水（0）——相当于"淹没"它
  3. 上下左右有陆地？继续淹没（递归！）
  4. 整座岛都被淹没了 → 计数器 +1
  5. 继续找下一块没被淹没的陆地……

每一块陆地只被淹没一次，每一座岛只计数一次。 这就是"逛遍整座岛"的威力！

动手实现：淹没整座岛 ​

ts
const map = [
  [1, 1, 0, 0, 0],
  [1, 1, 0, 0, 0],
  [0, 0, 1, 0, 0],
  [0, 0, 0, 1, 1],
]

// 从 (x, y) 开始，把整座岛淹没（1 变成 0）
function drown(x: number, y: number): void {
  // 出界了？已经是海水？返回
  if (x < 0 || x >= map.length || y < 0 || y >= map[x].length || map[x][y] !== 1) {
    return
  }

  map[x][y] = 0                        // 淹没这一格

  drown(x + 1, y)                      // 继续淹没：下
  drown(x - 1, y)                      // 上
  drown(x, y + 1)                      // 右
  drown(x, y - 1)                      // 左
}

// 数岛：找到一块陆地就淹没一座岛，计数器 +1
function countIslands(): number {
  let count = 0
  for (let x = 0; x < map.length; x++) {
    for (let y = 0; y < map[x].length; y++) {
      if (map[x][y] === 1) {
        count++                        // 发现一座新岛！
        drown(x, y)                    // 整座岛淹没，不再重复数
      }
    }
  }
  return count
}

console.log("岛的数量：" + countIslands())

输出：

岛的数量：3

3 座！对了！

看 drown——它就是第 23 章迷宫程序的"亲戚"：同样的"出界检查"、 同样的"四个方向递归"。不同的是：迷宫要找路，所以走不通要 擦掉脚印（回溯）；数岛要逛遍，所以走完的格子直接 淹没（不再回来）。

跑起来：逛一遍，看看淹了哪些 ​

给 drown 加一点"日志"，看看它是怎么逛的：

ts
// 加日志的版本：每淹没一格就喊一声
function drownLog(x: number, y: number): void {
  if (x < 0 || x >= map.length || y < 0 || y >= map[x].length || map[x][y] !== 1) {
    return
  }
  map[x][y] = 0
  console.log("淹没 (" + x + "," + y + ")")
  drownLog(x + 1, y)
  drownLog(x - 1, y)
  drownLog(x, y + 1)
  drownLog(x, y - 1)
}

const map2 = [
  [1, 1, 0],
  [1, 0, 0],
  [0, 0, 1],
]
console.log("开始淹没第一座岛：")
drownLog(0, 0)
console.log("第一座岛淹完了。还剩的陆地：")
for (let x = 0; x < map2.length; x++) {
  console.log(map2[x].join(" "))
}

输出：

开始淹没第一座岛：
淹没 (0,0)
淹没 (1,0)
淹没 (0,1)
第一座岛淹完了。还剩的陆地：
0 0 0
0 0 0
0 0 1

看 DFS 的路线：(0,0) → 下(1,0) → 上？(1,0) 的上是 (0,0)，已淹 → 右？(1,1) 是海水 → 左？出界 → 回到 (0,0) → 右 (0,1) → 四处看看全淹了 → 停。

一条路走到黑，走不动就回头——四个方向都试过才罢休。 第一座岛（3 格）全淹没了，地图上只剩右下角那块陆地， 下一轮数岛就会把它也淹了（第二座岛）。

BFS 和 DFS：两种逛法 ​

同样是把地图逛遍，BFS 和 DFS 的"姿势"完全不同：

BFS（第 26 章）DFS（本章）
怎么走一圈一圈扩散（队列）一条路走到黑（递归/栈）
找到的东西最短的路随便一条路 / 逛遍所有
适合最少换乘、最短路径数岛、遍历、回溯搜索

数岛用哪个都行（每个格子都会被逛到），但 DFS 的代码更短更直接 （递归几行搞定）；而"最短路径"必须用 BFS（DFS 找到的路可能是 绕远的）。

结语：27 章，一本完整的算法地图！ ​

恭喜你！你把这本《小探险家学算法》全部 27 章读完了。 回头看一眼你走过的路：

  • 基础篇：数步数（复杂度 O(1)/O(log n)/O(n)）、数组、字符串、 循环、函数
  • 数据结构篇：栈（撤销）、队列（叫号）、哈希表（闪电查找）、 链表（火车）
  • 查找与排序篇：线性查找、二分查找、冒泡/选择/插入排序、递归
  • 进阶篇：快速/归并/计数排序、二叉树、二叉搜索树、堆
  • 高手篇：分治（快速选择）、回溯（迷宫）、贪心（找零）、 动态规划（爬楼梯）、图（BFS/DFS）

现在，你已经拥有了一套完整的"算法工具箱"：

  • 看到问题，先想：能不能拆小？（递归、分治）
  • 要最短/最近：BFS 或 动态规划
  • 要试遍所有可能：回溯 或 DFS
  • 要每一步都最优：贪心（记得找反例！）
  • 数据怎么存：数组、Map、栈、队列、链表、树、堆、图

继续前进的路，就在脚下：

  • 去把 hello-algo（你参考过的《Hello 算法》）翻一翻——里面的 很多章节你已经懂了！
  • 去刷两道"力扣"的入门题，试试你的工具箱
  • 去参加一次编程比赛，认识更多小伙伴
  • 或者，把这本书里的小项目改造成你自己的作品——点名器、 密信、迷宫、地铁图……它们都在等你升级！

后会有期，小探险家！

小挑战 ​

  1. 数房间：把"数岛"改成"数房间"——一张图里，0 是地板、 1 是墙，上下左右连通的 0 组成一个房间。数一数有几个房间 （提示：把 drown 里的"淹没 1"改成"淹没 0"就行了！）。
  2. 最大岛：改造数岛程序，顺便记录最大的那座岛有几块陆地 （提示：drown 淹没了几格，就返回几——一座岛的面积）。
  3. 走迷宫最短路径：把第 23 章的迷宫，用 BFS 解一遍， 和 DFS 找到的路比一比，是不是一样短？（提示：BFS 在迷宫上 就是"第 26 章的地铁图"，把每个格子当成一个站！）

课后练习 ​

第 1 题（动手题）：我画的地图 ​

自己画一张 5×5 的地图（至少 3 座岛，用 1/0 表示）， 用 countIslands 数一数，手动验证。

参考答案（点开查看）

示例地图：

ts
const map = [
  [1, 0, 1, 0, 1],
  [1, 0, 0, 0, 1],
  [0, 0, 1, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 0, 0],
]
  • 左上角 2 格：岛 1
  • 右上角 2 格：岛 2
  • 中间 1 格：岛 3
  • 左下角 3 格（连一起）：岛 4

共 4 座岛。程序输出应该也是 4。

验证方法：自己圈出所有"上下左右相连"的 1，数一数有几团。 注意 (2,2) 和 (3,1)(3,2)(3,3) 是斜着的——不算相连！只有 上下左右才算。

第 2 题（思考题）：为什么淹没能避免重复数？ ​

drown 把 1 变成 0。想一想：如果不淹没（数完不标记）， 会怎样？

参考答案（点开查看）

不淹没的话，countIslands 的外层循环逛到同一座岛的 每一块陆地时，都会认为"发现了一座新岛"——一座 100 格的岛 会被数成 100 座！

淹没 = 给逛过的陆地做记号。这正是 DFS/BFS 的通用规矩： 逛过的地方做记号，绝不再逛（第 26 章的 visited 清单、 迷宫里的"脚印"都是记号）。记号一变（1→0），下次再遇到， 程序就知道"这座岛数过了"。

数岛、走迷宫、找最短路径……所有图算法都靠记号避免重复劳动。

第 3 题（思考题）：DFS 会无限循环吗？ ​

drown 里，如果不小心漏掉 map[x][y] = 0（淹没）这一行， 程序会怎样？会死循环吗？

参考答案（点开查看）

会死循环（或者说，无限递归直到栈溢出——第 15 章的教训！）。

没有淹没（标记），drown(0,0) 会去调用 drown(1,0)， drown(1,0) 又会调用 drown(0,0)（它的"上"）—— 两个函数互相调用，永远停不下来，直到第 15 章说的 "调用栈爆炸"。

标记（淹没、脚印、visited）是 DFS 的刹车。 写递归/搜索，第一件事就是检查：每一步都会让"没处理的部分" 变小吗？还是又绕回去了？

还有最后一章：《陷阱大冒险》——老师的考前错题本。 20 个"新手必踩 + 老手也翻车"的代码陷阱，考试前通读一遍， 这本书才算真正完结。走，去踩坑！