23. 迷宫探险（回溯）

知识点：回溯（backtracking）—— 试一步，不行就退回来（撤销选择）

项目：让程序走出迷宫

---

故事开场：迷宫里的"后悔药"

游乐园有个超级迷宫，你兴冲冲地钻了进去。可是走了几个弯，你发现—— 迷路了！前面是死路，你想退回刚才的分岔口，换一条路走。

"要是我能记住来时的路就好了……"你心想，"走错了就退回去， 退到分岔口再换一条路。"

这个"走错了就退回来"的本领，就是探险家最珍贵的武器。老师说：

"我们把迷宫搬进电脑，让程序也学会走错了就退回来—— 这个办法有个响亮的名字，叫回溯（backtracking）。"

---

笨办法先行：一条路走到黑

你写程序时，第一个想法是"挑一个方向一直走"：

// 迷宫：0 是路，1 是墙（入口在左上角，出口在右下角）
const maze = [
  [0, 1, 0, 0, 0],
  [0, 1, 0, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0],
]

// 从 (0,0) 出发，永远只往下走、往右走……
let x = 0
let y = 0
while (true) {
  console.log("(" + x + "," + y + ")")
  if (x === 4 && y === 4) {
    console.log("到出口了！")
    break
  }
  if (x + 1 < 5 && maze[x + 1][y] === 0) {
    x++                       // 能下就下
  } else if (y + 1 < 5 && maze[x][y + 1] === 0) {
    y++                       // 不能下就往右
  } else {
    console.log("撞墙了，走不动了！")
    break
  }
}

跑一下，输出：

(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(1,2)
(0,2)
(0,3)
(0,4)
(1,4)
(2,4)
(3,4)
(4,4)
到出口了！

咦，居然走出去了？这是你运气好——这条迷宫的路"碰巧"是一条 能一直下、一直右的路径。可老师摇了摇头，把迷宫改成了：

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

"全是路，没墙了！"老师说，"可你的程序只会'下、右、下、右'—— 走到 (4,4) 之前，还有 4 个格子它根本不会去。你迷宫的出口， 碰巧在'下右下右'这条线上吗？"

你愣住了："如果出口藏在左边……我的程序永远找不到！"

"一条路走到黑"的毛病：选了方向就不回头，遇到死路只会放弃， 不会退回去换。 这就是为什么需要"后悔药"。

---

引出知识点：回溯——试、退、再试

回溯的秘诀只有一句话：

走一步，试试；不行，就退回来（撤销），换一条路再试。

具体到迷宫：

1. 站在一个格子上，试四个方向（下、右、上、左）
2. 往前走一步，递归地试这条路能不能到出口
3. 这条路走不通 → 退回来，把踩过的标记擦掉（撤销），试下一个方向
4. 四个方向都试完还不行 → 这个格子不是正确答案，退到更前面

"退回来 + 撤销"是回溯的灵魂——它保证： 每一条路都被试过，而且试过的路不会留下'脏脚印'影响后面的尝试。

（还记得第 15 章递归、第 6 章撤销吗？回溯 = 递归 + 撤销，老熟人！）

---

动手实现：会后悔的迷宫程序

把迷宫搬进程序，配上"标记脚印"和"擦掉脚印"：

// 迷宫：0 是路，1 是墙；入口 (0,0)，出口 (4,4)
const maze = [
  [0, 1, 0, 0, 0],
  [0, 1, 0, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0],
]

// 从 (x, y) 出发找出口。找到返回 true，这条路走不通返回 false
function solveMaze(x: number, y: number): boolean {
  // 出界、撞墙、已经踩过 → 此路不通
  if (x < 0 || x >= 5 || y < 0 || y >= 5 || maze[x][y] !== 0) {
    return false
  }

  if (x === 4 && y === 4) {
    console.log("(" + x + "," + y + ")")    // 到出口了！
    return true
  }

  maze[x][y] = 2                    // 踩上去：留下脚印（2 = 走过的路）

  // 试四个方向：下、右、上、左（哪个方向能到出口？）
  if (solveMaze(x + 1, y)) { console.log("(" + x + "," + y + ")"); return true }
  if (solveMaze(x, y + 1)) { console.log("(" + x + "," + y + ")"); return true }
  if (solveMaze(x - 1, y)) { console.log("(" + x + "," + y + ")"); return true }
  if (solveMaze(x, y - 1)) { console.log("(" + x + "," + y + ")"); return true }

  maze[x][y] = 0                    // 擦掉脚印：这条路不通，退回去！
  return false
}

solveMaze(0, 0)

输出（从出口倒着打印回入口的路径）：

(4,4)
(3,4)
(3,3)
(3,2)
(4,2)
(4,1)
(4,0)
(3,0)
(2,0)
(1,0)
(0,0)

程序走出迷宫了！ 注意看这条路线——它绕到了地图最下面， 从底部钻过去的！因为程序按"下、右、上、左"的顺序试， 下面这条弯弯曲曲的路先被探到了。把迷宫打印出来，看看脚印（2） 画出的路：

// 打印迷宫：1 是墙，2 是走过的路
for (let x = 0; x < maze.length; x++) {
  let line = ""
  for (let y = 0; y < maze[x].length; y++) {
    line = line + maze[x][y] + " "
  }
  console.log(line)
}

输出：

2 1 0 0 0
2 1 0 1 0
2 0 0 1 0
2 1 2 2 2
2 2 2 1 0

看！脚印连成了一条路：从 (0,0) 一路下到地图底部，再右拐、 上拐，弯弯曲曲钻到 (4,4)。而那些"0"——是程序试过又退回来的地方： 踩过，擦了，所以还是 0。

---

跑起来：回溯到底试了多少条路？

在 solveMaze 里加一个计数器，看看它总共"踩"了多少次格子：

let tries = 0

function solveMazeCount(x: number, y: number): boolean {
  tries++
  if (x < 0 || x >= 5 || y < 0 || y >= 5 || maze[x][y] !== 0) {
    return false
  }
  if (x === 4 && y === 4) {
    return true
  }
  maze[x][y] = 2
  if (solveMazeCount(x + 1, y)) { return true }
  if (solveMazeCount(x, y + 1)) { return true }
  if (solveMazeCount(x - 1, y)) { return true }
  if (solveMazeCount(x, y - 1)) { return true }
  maze[x][y] = 0
  return false
}

solveMazeCount(0, 0)
console.log("一共试了 " + tries + " 步（包括撞墙）")

输出：

一共试了 17 步（包括撞墙）

25 个格子，只走了 17 步——因为每块格子最多踩一次： 撞墙立刻回头，死路及时擦脚印，绝不重复劳动。它把"该试的路" 都试了一遍，不多走一步。

回溯的代价：如果问题"没有记忆"（比如八皇后、数独——放下的 棋子不能简单"擦掉"，因为影响全局），回溯要试遍所有组合， 最坏是指数级的（O(2ⁿ) 级别）；迷宫这种"有记忆"的问题 （踩过就标记），回溯反而很省——每格最多踩一次。 聪明人还会用"剪枝"（提前发现走不通就立刻退）让回溯更快一些。 你已经掌握计算机解决难题的最重要武器之一了！

---

小挑战

1. 八皇后：8×8 的国际象棋棋盘上放 8 个皇后，谁都不能吃谁 （同一行、同一列、同一斜线上不能有两个皇后）。 用回溯的思路想：第一行皇后放哪一列？试每一列，放上去， 下一行再试……放不下就退回来换一列。这就是著名的"八皇后问题"， 网上搜搜，看看别人怎么用代码解的！
2. 换方向：把 solveMaze 的尝试顺序从"下、右、上、左"改成 "左、上、右、下"，跑一跑，找到的路一样吗？为什么？
3. 数数路：改一改程序，数一数从入口到出口一共有几条不同的路 （提示：不找到就停，而是找到后继续试别的方向——把所有路都数出来）。

---

课后练习

第 1 题（动手题）：我的小迷宫

自己设计一个 4×4 的迷宫（至少 3 堵墙，入口 (0,0)，出口 (3,3)）， 用 solveMaze 解出来，打印路径。

参考答案（点开查看）

一个可行的迷宫：

const maze = [
  [0, 0, 0, 1],
  [1, 1, 0, 1],
  [0, 0, 0, 0],
  [0, 1, 1, 0],
]

solveMaze(0, 0) 会找到一条路（比如下、右、右、下、下、右）。 打印迷宫后，脚印（2）连成的线就是路径。

验证方法：自己用手沿着 2 走一遍，从 (0,0) 到 (3,3)， 每一步都在 0/2 上、不穿墙——就对了。

第 2 题（思考题）：为什么必须"擦掉脚印"？

maze[x][y] = 0（擦掉脚印）这一步，如果删掉会怎样？ （提示：删掉后程序还能不能找到路？试试运行。再想想"数一数有几条 不同的路"（小挑战 3）会变成什么。）

参考答案（点开查看）

删掉后，找"一条路"的迷宫程序依然能找到出口（试试就知道）—— 因为"踩过就标记、不重复踩"本来就是一种搜索（它就是普通的 DFS）， 找到一条路绰绰有余。这个 bug 藏得很深！

那"擦掉脚印"到底有什么用？再看两个场景：

• 数一数有几条不同的路：不擦的话，每块格子只能被第一条路踩过， 后面的路全被脚印堵住——答案永远只有"1 条"！
• 八皇后、数独：放下的棋子"踩过不擦"，后面的皇后就没地方放了， 所有解都会漏掉。

所以"撤销"是回溯的灵魂：找"一条路"不需要它，找"所有解"没有它不行。 （下次你在程序里漏了撤销，程序还能跑——这就是它特别难排查的原因！）

第 3 题（思考题）：回溯 vs 贪心

"走一步，不行就退回来"（回溯）和"每次选最好的方向往前走" （贪心——下一章的主角）有什么区别？哪种更"稳妥"？

参考答案（点开查看）

• 贪心：只看眼前，选当下最好的选择，永不回头。 快（每次都一步决定），但可能"眼前是对的，全局是错的"。
• 回溯：所有路都试一遍，错了就退回来重试。 稳（一定能找到答案），但慢（要试遍所有可能）。

迷宫这种"路有多条、选错会死"的问题，贪心可能一头撞进死路； 回溯虽然慢，但保证能找到出口（如果存在的话）。

用贪心的时机：确定"眼前最优 = 全局最优"的问题（下一章见！）。 用回溯的时机：没有捷径、只能试试看的难题（迷宫、数独、八皇后）。

---

下一课预告：自动售货机要找给顾客 47 元。硬币有 25、10、5、1 元。 有个急性子算法说："每次都拿最大的硬币！"——47 元：25、10、10、 1、1，5 枚搞定。听起来聪明极了。可是……如果硬币只有 1、3、4 元， 要凑 6 元，这个"每次都拿最大"的办法，还是最好的吗？