CSP-J 2026 第一轮 第 8 题：从 S 出发做广度优先搜索（BFS）

题目

下图为 $5 \times 5$ 网格，行号、列号均从 0 开始，# 为障碍，. 为可通行格：

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

S..#.
...#.
...#.
##..E
...#.

选项

• A. 15
• B. 12
• C. 14
• D. 13

答案

C

题解

选 C，14 个。

关键是：格子入队时就标记为已访问；E 第一次入队时立即停止计数。

用 (行号, 列号) 表示位置，按“上、下、左、右”的顺序搜索，各层的入队顺序如下：

最后几步尤其重要：

• 取出 (3,2) 时，先把下方的 (4,2) 入队，再把右方的 (3,3) 入队。
• 因此先处理 (4,2)，将 (4,1) 入队。
• 再处理 (3,3)，将 E 入队，此时停止。(4,1) 还没出队，所以 (4,0) 尚未入队。

总数为： \[ 1+2+3+2+1+1+2+2=\boxed{14} \]