CSP-J 入门级 · CSP 2026 入门级第一轮 第 8 题

【单选】下图为 5×5 网格，行号、列号均从 0 开始，# 为障碍，. 为可通行格。从 S 出发做广度优先搜索（BFS）：初始时把 S 入队；每次取出队首格子，按“上、下、左、右”的顺序遍历它的四个相邻格子，越界、障碍或已访问的格子跳过，其余格子标记为已访问并入队。当 E 第一次入队时，已经入队过的格子（含 S 和 E）共有多少个（ ）。

严格按题面给的顺序"上、下、左、右"模拟 BFS 队列，把每次新入队的格子编号（1 是 S）。注意"E 第一次入队"就是问 E 是第几个被入队的格子。

把邻居顺序改成常见的"上下左右"之外（如先左右后上下）导致编号错位；或把已访问标记放在出队时才做，造成重复入队；也容易忘掉"S 和 E 自身都算"。

这道题在问什么

在一张 5×5 的网格上，从起点 S 出发做广度优先搜索（BFS），按题目规定的“上、下、左、右”顺序扩展邻居。问的是：当终点 E 第一次被放入队列时，从开始到此刻，队列里一共放进去过多少个格子（S 和 E 都要算上）？

逐个解释

• BFS（广度优先搜索）：一层一层向外扩展的搜索方式——先把起点入队，之后反复“取出队首格子、把它的可通行邻居入队”，直到能走到的格子都访问完。
• “上、下、左、右”顺序：每扩展一个格子，都严格按这个固定顺序检查它的四个邻居。顺序不同，入队先后就不同，最终编号也会变，所以必须照题面来。
• E 第一次入队：终点 E 被某个已出队的格子扩展、首次放进队列的那一刻。
• “已经入队过的格子（含 S 和 E）”：从 S 开始到 E 入队为止，所有被放进过队列的格子，S 和 E 自身都算。

网格与规则

行号、列号从 0 开始，障碍（#）位于 (0,3)、(1,3)、(2,3)、(3,0)、(3,1)、(4,3)，S 在 (0,0)，E 在 (3,4)：

行\列  0    1    2    3    4
 0    S    .    .    #    .
 1    .    .    .    #    .
 2    .    .    .    #    .
 3    #    #    .    .    E
 4    .    .    .    #    .

邻居按 上、下、左、右 顺序考察；越界 / 障碍 / 已访问一律跳过；被访问的格子标记并入队。

怎样模拟 BFS（逐步入队）

把每次新入队的格子依次编号（S 是第 1 个）。下面每一行记：这一轮“出队的是谁”，以及按“上、下、左、右”新入队了谁（跳过越界、障碍、已访问）：

E 第一次入队时编号为 14，即“已经入队过的格子（含 S 和 E）”共 14 个，选 C。

其他选项为什么错

• D. 13：漏算 S 或漏算 E 自身；
• B. 12 / A. 15：邻居顺序或障碍位置记错（例如把 (4,1) 误当障碍，或把 (0,2) 的右邻当成可通行）。

记忆点

• BFS 的“层序”不等于“按距离排序的编号”：同一层内先被谁扩展，取决于入队顺序，而入队顺序又由邻居遍历顺序决定，所以题面的“上、下、左、右”是必须严格执行的条件；
• 计数类题目建议画表格记录编号，比心算稳得多。