下面我们用队列解决迷宫问题。程序如下：

例 12.4. 用广度优先搜索解迷宫问题

运行结果如下：

其实仍然可以像一样用数组表示每个点的前趋，但我想换一种更方便的数据结构，直接在每个点的结构体中加一个成员表示前趋：

图 12.3. 广度优先搜索的队列数据结构

为了帮助理解，我把这个算法改写成伪代码如下：

从打印的搜索过程可以看出，这个算法的特点是沿各个方向同时展开搜索，每个可以走通的方向轮流往前走一步，这称为广度优先搜索（BFS，Breadth First Search）。探索迷宫和队列变化的过程如下图所示。

广度优先是一种步步为营的策略，每次都从各个方向探索一步，将前线推进一步，图中的虚线就表示这个前线，队列中的元素总是由前线的点组成的，可见正是队列先进先出的性质使这个算法具有了广度优先的特点。广度优先搜索还有一个特点是可以找到从起点到终点的最短路径，而深度优先搜索找到的不一定是最短路径，比较本节和上一节程序的运行结果可以看出这一点，想一想为什么。

1、本节的例子直接在队列元素中加一个指针成员表示前趋，想一想为什么上一节的例 12.3 “用深度优先搜索解迷宫问题”不能采用这种方法表示前趋？

2、本节例子中给队列分配的存储空间是512个元素，其实没必要这么多，那么解决这个问题至少要分配多少个元素的队列空间呢？跟什么因素有关？