[面经] Meta Coding：没有地图的迷宫找奶酪（DFS + 回溯）高频题
冷目灼灼的扁豆
[面经] Meta Coding：没有地图的迷宫找奶酪（DFS + 回溯）
我的 Meta 面经第二题。这题有意思的地方在于没有地图、没有全局状态：迷宫只能靠一步步走出来。
题目
一只老鼠在迷宫里找奶酪。你只有两个函数可用：
实现
思路
相对坐标 + DFS + 回溯：
易错点
有问题欢迎讨论。
我的 Meta 面经第二题。这题有意思的地方在于没有地图、没有全局状态：迷宫只能靠一步步走出来。
题目
一只老鼠在迷宫里找奶酪。你只有两个函数可用：
has_cheese()：老鼠当前在奶酪格时返回 True，否则 False。move(direction)：朝指定方向走一步。走成功返回 True，撞墙返回 False（位置不变）。
# 是墙，M 是起点，C 是奶酪）：######
#M #
# ## #
# C #
# #
######
#M #
# ## #
# C #
# #
######
实现
find_cheese()，把老鼠带到奶酪处。思路
相对坐标 + DFS + 回溯：
- 用相对起点的坐标 (0, 0) 记录老鼠的位置。每次 move 成功，坐标加上对应方向的偏移，这样你始终知道自己相对出发点在哪。
seen存走过的相对坐标，防止绕圈。- 每到一格先查
has_cheese()。然后逐个方向尝试：去过的格子跳过，没去过的先move过去再递归；如果递归无功而返（死路），就朝来时的方向move回去，再试下一个方向。 - 方向表按上/下/左/右排列，第
i个方向的反方向正好是i ^ 1，回溯时不用再查一张反方向表。
# Ordered so that index i ^ 1 is always the reverse move:
# up <-> down, left <-> right.
MOVES = [
("up", 0, -1),
("down", 0, 1),
("left", -1, 0),
("right", 1, 0),
]
def find_cheese():
seen = set()
def walk(x, y):
if has_cheese():
return True
seen.add((x, y))
for i, (name, dx, dy) in enumerate(MOVES):
nx, ny = x + dx, y + dy
if (nx, ny) in seen:
continue
if not move(name):
continue # wall: position unchanged, do not mark that cell
if walk(nx, ny):
return True
move(MOVES[i ^ 1][0]) # step back the way we came
return False
return walk(0, 0)
# up <-> down, left <-> right.
MOVES = [
("up", 0, -1),
("down", 0, 1),
("left", -1, 0),
("right", 1, 0),
]
def find_cheese():
seen = set()
def walk(x, y):
if has_cheese():
return True
seen.add((x, y))
for i, (name, dx, dy) in enumerate(MOVES):
nx, ny = x + dx, y + dy
if (nx, ny) in seen:
continue
if not move(name):
continue # wall: position unchanged, do not mark that cell
if walk(nx, ny):
return True
move(MOVES[i ^ 1][0]) # step back the way we came
return False
return walk(0, 0)
易错点
move失败（撞墙）时位置不变：不要更新坐标，也不要把墙对面的格子标记为已访问，它可能从另一边绕得到。- 回溯必须真的
move回去。如果记账的坐标和老鼠的实际位置脱节，后面全错。 seen记的是相对坐标，不是路径：同一格从不同路线到达只算一次。- 递归深度最坏等于格子数。迷宫很大时改成显式栈，思路不变。
有问题欢迎讨论。
共0条回复
