[面经] Meta Coding：没有地图的迷宫找奶酪（DFS + 回溯）

[面经] Meta Coding：没有地图的迷宫找奶酪（DFS + 回溯）
我的 Meta 面经第二题。这题有意思的地方在于没有地图、没有全局状态：迷宫只能靠一步步走出来。
题目
一只老鼠在迷宫里找奶酪。你只有两个函数可用：

• 1. has_cheese()

  复制代码
  ：老鼠当前在奶酪格时返回 True，否则 False。
• 1. move(direction)

  复制代码
  ：朝指定方向走一步。走成功返回 True，撞墙返回 False（位置不变）。

迷宫示例（

1. #

复制代码

是墙，

1. M

复制代码

是起点，

1. C

复制代码

是奶酪）：

1. ######
2. #M   #
3. # ## #
4. #  C #
5. #    #
6. ######

复制代码

实现

1. find_cheese()

复制代码

，把老鼠带到奶酪处。
思路
相对坐标 + DFS + 回溯：

• 用相对起点的坐标 (0, 0) 记录老鼠的位置。每次 move 成功，坐标加上对应方向的偏移，这样你始终知道自己相对出发点在哪。
• 1. seen

  复制代码
  存走过的相对坐标，防止绕圈。
• 每到一格先查
  1. has_cheese()

  复制代码
  。然后逐个方向尝试：去过的格子跳过，没去过的先
  1. move

  复制代码
  过去再递归；如果递归无功而返（死路），就朝来时的方向
  1. move

  复制代码
  回去，再试下一个方向。
• 方向表按上/下/左/右排列，第
  1. i

  复制代码
  个方向的反方向正好是
  1. i ^ 1

  复制代码
  ，回溯时不用再查一张反方向表。

代码

1. # Ordered so that index i ^ 1 is always the reverse move:
2. # up <-> down, left <-> right.
3. MOVES = [
4.     ("up", 0, -1),
5.     ("down", 0, 1),
6.     ("left", -1, 0),
7.     ("right", 1, 0),
8. ]
10. def find_cheese():
11.     seen = set()
13.     def walk(x, y):
14.         if has_cheese():
15.             return True
16.         seen.add((x, y))
17.         for i, (name, dx, dy) in enumerate(MOVES):
18.             nx, ny = x + dx, y + dy
19.             if (nx, ny) in seen:
20.                 continue
21.             if not move(name):
22.                 continue  # wall: position unchanged, do not mark that cell
23.             if walk(nx, ny):
24.                 return True
25.             move(MOVES[i ^ 1][0])  # step back the way we came
26.         return False
28.     return walk(0, 0)

复制代码

易错点

• 1. move

  复制代码
  失败（撞墙）时位置不变：不要更新坐标，也不要把墙对面的格子标记为已访问，它可能从另一边绕得到。
• 回溯必须真的
  1. move

  复制代码
  回去。如果记账的坐标和老鼠的实际位置脱节，后面全错。
• 1. seen

  复制代码
  记的是相对坐标，不是路径：同一格从不同路线到达只算一次。
• 递归深度最坏等于格子数。迷宫很大时改成显式栈，思路不变。

复杂度：每个格子最多进入一次，O(格子数）。
有问题欢迎讨论。