GESP 七级 · GESP202609 C++ 七级 第 8 题

在二维网格上实现泛洪填充时，为了防止递归层数过深，最适合的非递归实现方式是（　　）。

递归版泛洪填充本质是用系统调用栈隐式管理待访问格子，但网格连通区域可能很大，递归深度会爆栈。非递归实现必须显式用数据结构替代系统栈：BFS 用队列按层扩展，DFS 用栈按深度扩展。这样无论连通块多大，内存占用都是 O(网格尺寸) 而非 O(递归深度)。

选项 A 哈希表只记录访问次数，无法控制遍历顺序，不能替代栈/队列；选项 B 快速排序是排序算法，与泛洪填充的遍历无关；选项 C 二分查找需要有序序列，网格无此性质。考生易混淆"记录访问"与"控制遍历"两个不同需求，误以为哈希表能解决深度问题。

1. 考纲定位

本题考查《GESP 七级 C++ 考试大纲》算法模块中的图遍历与递归优化。命题人卡住的是考生对"递归栈溢出"这一底层限制的理解——七级不再满足于写出递归代码，而是要求能识别递归的代价并给出替代方案。

2. 解题思维

泛洪填充是典型的图遍历问题：把每个格子看作节点，相邻格子连边。递归版用系统栈隐式管理待访问节点，但系统栈深度有限。非递归实现必须显式用数据结构替代系统栈：BFS 用队列按层扩展，DFS 用栈按深度扩展。这样无论连通块多大，内存占用都是 O(网格尺寸) 而非 O(递归深度)。