如何实现树结构的广度优先搜索？DMOPC14C1P5求解困惑

阿华AIGC实验室

2026-5-21

搞定DMOPC14C1P5：BFS实现全指南

嘿，我来帮你理清楚这个问题的BFS实现思路！首先直接给你明确几个关键点：

先答你的核心疑问：BFS完全不需要递归

递归一般是深度优先搜索（DFS）的常用写法，但BFS是基于队列的迭代算法，用递归反而会搞复杂，还容易出现栈溢出的问题——毕竟BFS是逐层遍历，递归的栈深度根本跟不上队列的广度。所以放心，咱们用迭代写法就行，完全不用递归。

在线OJ提交不用搞复杂类结构

网上的方案用类可能是为了代码复用或者结构清晰，但在OJ上提交完全没必要这么麻烦，用简单的数组和队列就能搞定。下面给你拆解具体步骤：

1. 先理清楚问题本质

这个问题是带高度约束的网格最短路径：从起点出发，每次只能走上下左右四个方向，且相邻格子的海拔差不能超过给定的D，求到终点的最少步数。BFS天生适合这种无权图的最短路径问题，因为它是按层遍历，第一次到达终点的路径就是最短的。

2. 实现的核心准备

网格存储：用二维数组存每个格子的海拔高度。
访问标记数组：和网格一样大的二维布尔数组，记录每个格子是否已经被访问过——BFS第一次到某个格子的路径就是最短的，后续再遇到就不用处理了，避免重复入队浪费时间。
队列：用来存待处理的格子信息，每个元素要包含当前的x坐标、y坐标，以及走到这里用了多少步。比如Python里用元组(x, y, steps)就行，C++可以用结构体或者嵌套pair。
方向偏移量：四个方向的坐标变化，比如dx = [-1,1,0,0]，dy = [0,0,-1,1]，这样循环四次就能遍历上下左右四个邻居。

3. BFS的执行流程

初始化：把起点坐标和初始步数0放进队列，同时标记起点为已访问。
循环处理队列：
- 取出队列最前面的元素（当前位置和步数）。
- 如果当前位置就是终点，直接输出步数，结束程序——这就是最短路径。
- 遍历四个方向的邻居：
  - 计算邻居的新坐标nx和ny。
  - 检查新坐标是否在网格范围内（不能越界）。
  - 检查这个邻居有没有被访问过。
  - 检查当前格子和邻居的海拔差绝对值是否≤D。
  - 满足所有条件的话，标记邻居为已访问，把它和步数+1放进队列。
无法到达的情况：如果队列都空了还没找到终点，说明走不通，输出-1。

示例代码（Python版，适配OJ提交）

from collections import deque
import sys

def main():
    # 快速读取输入，避免超时
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    D = int(data[idx])
    idx += 1
    
    grid = []
    for _ in range(N):
        row = list(map(int, data[idx:idx+M]))
        idx += M
        grid.append(row)
    
    # 读取起点和终点（注意题目坐标是1-based，转成0-based）
    sx = int(data[idx]) - 1
    idx += 1
    sy = int(data[idx]) - 1
    idx += 1
    ex = int(data[idx]) - 1
    idx += 1
    ey = int(data[idx]) - 1
    idx += 1
    
    # 初始化访问标记和队列
    visited = [[False]*M for _ in range(N)]
    q = deque()
    q.append( (sx, sy, 0) )
    visited[sx][sy] = True
    
    # 四个方向
    dirs = [ (-1,0), (1,0), (0,-1), (0,1) ]
    
    while q:
        x, y, steps = q.popleft()
        # 到达终点，直接输出步数
        if x == ex and y == ey:
            print(steps)
            return
        # 遍历所有方向
        for dx, dy in dirs:
            nx = x + dx
            ny = y + dy
            # 检查边界、访问状态、高度差
            if 0 <= nx < N and 0 <= ny < M:
                if not visited[nx][ny] and abs(grid[x][y] - grid[nx][ny]) <= D:
                    visited[nx][ny] = True
                    q.append( (nx, ny, steps + 1) )
    
    # 队列空了还没找到终点，输出-1
    print(-1)

if __name__ == "__main__":
    main()