第十三单元：图遍历 · 深度优先搜索与连通路径

封神冰川的关口前,食人魔布下了密密麻麻的雷区来保护他们的酋长。这些地雷有个致命弱点——只要点燃一颗,它就会像多米诺骨牌一样,把上下左右相邻的地雷逐个引爆,形成一条蔓延的火线。你的任务,就是找出哪一列的地雷能一路连锁引爆、最终把火烧到酋长脚下。这本质上是一道经典的算法题:在网格上寻找一条连通的路径。这一单元虽然只有一个关卡,却是本课程数据结构的巅峰之作——你将掌握计算机科学中极其重要的图遍历技术,尤其是深度优先搜索(DFS)。

13.1.1 什么是图遍历（What Is Graph Traversal）

13.1.1.1 系统地访问所有能到达的节点 Systematically visit every reachable node

图(graph)是由节点(node)和连接节点的边(edge)组成的数据结构。图遍历(graph traversal)就是从某个起点出发,沿着边,系统地访问所有能到达的节点。它是解决"迷宫寻路""连通区域""社交网络关系""网页爬取"等无数问题的通用武器。本关的雷区,正是一张图:每颗地雷是一个节点,相邻的地雷之间有一条边。

13.1.2 网格即图（A Grid Is a Graph）

13.1.2.1 每个格子是节点，相邻格子有边 Each cell is a node; adjacent cells share an edge

本关的地图是一个字符串数组:每个字符 "x" 表示一颗地雷、"." 表示空地。这样的二维网格本身就是一张图——每个格子是节点,上下左右相邻且同为地雷的格子之间存在边。地图的第一行(索引 0)最靠近英雄/最靠上、酋长在这一侧;最后一行(底部)最靠近雷区起点。我们要找的,是一条从底部某颗地雷出发、能连通到顶部第 0 行的连锁路径。

13.2.1 DFS 的核心思想（The Core Idea of DFS）

13.2.1.1 一条路走到黑，再回头换路 Go as deep as possible, then backtrack

深度优先搜索(Depth-First Search, DFS)的策略是"不撞南墙不回头":从起点出发,沿着一条路径尽可能往深处走,直到走不通(没有未访问的邻居)为止;然后回退到上一个还有别的岔路的节点,换一条路继续深入。如此反复,直到访问完所有能到达的节点。这种"先深入、再回头"的探索方式,正是它名字的由来。

13.2.2 DFS vs BFS（Depth-First vs Breadth-First）

13.2.2.1 深度优先与广度优先的区别 The difference between DFS and BFS

图遍历有两大经典策略:深度优先搜索(DFS)用栈,一头扎到底再回头;广度优先搜索(BFS)用队列,像水波一样一圈圈向外扩散。对于"判断两点是否连通"这类问题,两者都能解决;本关采用 DFS + 栈的方案。有趣的是,把上一单元学的"栈"换成"队列",DFS 就变成了 BFS——它们的骨架几乎一样,区别只在于用什么容器存待访问节点。

13.3.1 栈驱动 DFS（Stack-Driven DFS）

13.3.1.1 栈的"后进先出"天然实现深入 A stack's LIFO nature naturally goes deep

DFS 的迭代实现靠一个栈(stack)来记录"接下来要访问的节点"。栈是后进先出(LIFO)的:最后放进去的最先取出。每次从栈顶取一个节点来处理,把它未访问的邻居们再压入栈顶——由于最新压入的邻居会最先被取出,程序自然就"顺着最新发现的路往深处钻",完美契合深度优先的行为。

13.3.2 push 与 pop（Push and Pop）

13.3.2.1 压入待访问、弹出来处理 Push what's to visit, pop to process

在关卡里,节点用 [row, col](行、列坐标)表示。核心操作两个:stack.push([row, col]) 把一个待访问节点压入栈顶;stack.pop() 从栈顶取出一个节点来处理。主循环 while len(stack):(栈非空)不断弹出、处理、再把新邻居压入,直到栈空——那时说明这一片连通区域已全部走完。

# DFS 的骨架:栈驱动的主循环
stack = []
visited = []

# 先把底行所有地雷作为起点压入栈
for j in range(width):
    if fieldMap[height - 1][j] == "x":
        stack.push([height - 1, j])

while len(stack):          # 栈非空就继续
    state = stack.pop()   # 取出栈顶节点
    row = state[0]
    col = state[1]
    # … 处理该节点、把邻居压入栈 …

13.4.1 避免重复访问（Avoid Revisiting）

13.4.1.1 没有 visited 就会无限循环 Without visited, you loop forever

网格里的邻接是双向的:A 是 B 的邻居,B 也是 A 的邻居。如果不做记录,程序会在 A、B 之间来回横跳、永远停不下来。解决办法是维护一个 visited 集合,记录已经处理过的节点。每次取出一个节点,先检查它是否已在 visited 里——若是,就 continue 跳过;否则把它加入 visited 再处理。这样每个节点最多处理一次,循环必然终止。

# 用 visited 防止重复访问、避免死循环
strPos = str(row) + "-" + str(col)   # 坐标转字符串
if strPos in visited:
    continue                    # 已访问过,跳过
visited.append(strPos)          # 标记为已访问

13.4.2 坐标字符串化（Stringifying Coordinates）

13.4.2.1 为什么用 "row-col" 表示坐标 Why represent a coordinate as "row-col"

判断"某坐标是否访问过",需要一种能可靠比较的表示方式。关卡把坐标 [row, col] 拼成一个字符串,如 "2-3",再放进 visited 判重。用字符串的好处是:同一个坐标永远生成同一个字符串,in 判断简单可靠,不用担心比较两个列表是否"相等"的麻烦。行列之间用分隔符(如 "-")隔开,能避免歧义——否则 1 和 12 拼接可能与 12 和 1 混淆。

13.5.1 上下左右偏移（Up/Down/Left/Right Offsets）

13.5.1.1 用偏移量数组枚举四个邻居 Enumerate four neighbors with an offset array

网格里每个格子有四个正交邻居:上、下、左、右(不含对角线,因为多米诺链式反应只在水平和垂直方向传播)。与其写四段重复代码,不如用一个偏移量数组 neighbourDiffs 统一枚举:每个偏移是 [行变化, 列变化]。遍历这个数组,把当前坐标加上偏移,就能依次得到四个邻居的坐标。

# 四方向偏移:上、下、左、右(无对角线)
neighbourDiffs = [[-1, 0], [1, 0], [0, -1], [0, 1]]

for diff in neighbourDiffs:
    neighRow = row + diff[0]   # 邻居的行
    neighCol = col + diff[1]   # 邻居的列
    # … 检查这个邻居 …

13.5.2 越界检查（Boundary Checks）

13.5.2.1 邻居可能跑到地图外面 A neighbor might fall outside the map

算出的邻居坐标可能超出地图边界——比如最左列的格子没有"左邻居",最上行的格子没有"上邻居"。必须先做越界检查:如果 neighRow 或 neighCol 小于 0,或者大于等于地图的高/宽,就 continue 跳过这个非法邻居。只有落在地图内、且是地雷 "x"、且未访问过的邻居,才值得压入栈继续探索。

# 越界检查 + 是否地雷 + 是否已访问
if neighRow < 0 or neighCol < 0 or neighRow >= height or neighCol >= width:
    continue                    # 跑出地图,跳过

strNeighPos = str(neighRow) + "-" + str(neighCol)
if strNeighPos in visited:
    continue                    # 已访问,跳过
if fieldMap[neighRow][neighCol] == "x":
    stack.push([neighRow, neighCol])   # 是地雷,压栈待访问

13.6.1 从底到顶找路径（Path from Bottom to Top）

13.6.1.1 到达第 0 行即为成功 Reaching row 0 means success

整个搜索的目标很明确:从底行(最后一行)的地雷出发,看能否连锁到达顶行(第 0 行)。因此在弹出每个节点处理时,先检查它的行号——一旦 row == 0,说明火线已经烧到了最靠近酋长的那一排,当前这一列就是答案!记下它的列号 resultColumn = col,然后 break 结束搜索。这就是把 DFS 用于"连通性判断"的关键落点。

# 到达顶部第 0 行 → 找到通往酋长的火线
if row == 0:
    resultColumn = col   # 记下这一列
    break                 # 找到答案,结束搜索

这一节聚焦关卡的策略、思路与算法设计,只展示用于说明的关键片段,完整通关程序请你自己动手完成。

第 30 关 · 匹配火线

🔥 匹配火线 —— DFS 寻找连锁引爆的路径

图2：匹配火线——雷区是字符串网格,用 DFS + 栈从底行地雷向上搜索,找出能连锁引爆到酋长(顶行)的那一列

策略:把雷区当成图,用 DFS 判断"哪列能连通到顶部"

侦察员给出雷区地图 fieldMap(字符串数组,"x" 是地雷、"." 是空地),第一行(索引 0)靠近酋长,最后一行靠近你。地雷会与上下左右相邻的地雷链式引爆。策略:从底行的每颗地雷出发做 DFS,沿相邻地雷向上蔓延,若能到达第 0 行,那一列就是能引爆酋长的火线。踩上那一列的地雷即可获胜。

思路拆解一:准备地图尺寸与起点

先取地图,算出 height = len(fieldMap) 和 width = len(fieldMap[0])。初始化空栈 stack 和空 visited。然后遍历底行(height - 1)每一列,把是地雷的格子作为起点 push([height-1, j]) 压入栈——这体现了"从底部开始搜索"的要求。

# 关键片段:尺寸 + 底行起点入栈
fieldMap = hero.findFriends()[0].getMap()
height = len(fieldMap)
width = len(fieldMap[0])
stack = []
visited = []

for j in range(width):
    if fieldMap[height - 1][j] == "x":
        stack.push([height - 1, j])   # 底行地雷 = 起点

思路拆解二:DFS 主循环 + 到顶判定

主循环 while len(stack): 弹出栈顶节点、拆出 row/col。先做到顶判定:若 row == 0 则记下 resultColumn = col 并 break。再做判重:坐标字符串化,若在 visited 就跳过,否则标记。这几步的先后顺序很关键——到顶判定应在判重之前,才能第一时间捕捉成功。

# 关键片段:主循环核心逻辑
while len(stack):
    state = stack.pop()
    row = state[0]
    col = state[1]
    strPos = str(row) + "-" + str(col)
    if row == 0:              # 到达顶部 → 成功
        resultColumn = col
        break
    if strPos in visited:      # 判重
        continue
    visited.append(strPos)
    # … 接着枚举四方向邻居并压栈(见 13.5)…

思路拆解三:把列号换算成坐标去踩雷

找到 resultColumn 后,用关卡给的常量把列号换算成实际的 X 坐标:resultX = resultColumn * mineDistance + firstXPos,再 moveXY 走过去踩上那颗地雷,引爆整条火线。逻辑与地图数据之间靠这套换算公式对齐。

# 关键片段:列号 → 坐标,前往引爆
resultX = resultColumn * mineDistance + firstXPos
hero.moveXY(resultX, hero.pos.y)   # 先横向对齐
hero.moveXY(resultX, firstYPos)     # 再踏上地雷

网格坐标与游戏坐标的桥梁：算法在"行列网格"里思考,游戏世界用"XY 米"定位。resultColumn * mineDistance + firstXPos 正是连接两者的桥——列号乘以雷距、再加上第一列的起始 X。理解这种"逻辑坐标 ↔ 物理坐标"的换算,是把算法落到实际场景的常见技能。

压栈时也要判重与判雷：为效率和正确性,压入邻居前最好先确认它是地雷、未访问且未越界。同时切记坐标拼接前用 str() 转换,并且四方向邻接不含对角线——多米诺只沿水平和垂直传播。

13.8.1 新手最容易踩的坑（Pitfalls for Beginners）

13.8.1.1 DFS 与网格遍历的典型问题 Typical issues with DFS and grid traversal

图3：忘记 visited 导致死循环、漏做越界检查、坐标未转字符串、含了对角线,是本单元最常见的失误