Lesson 36 - 广度优先解决迷宫问题

课程任务

队列是一组元素的集合，提供两种基本操作：Enqueue（入队）将元素添加到队尾，Dequeue（出队）从队头取出元素并返回。就像排队买票一样，先来先服务，先入队的人也是先出队的，这种方式称为FIFO（First In First Out，先进先出），有时候队列本身也被称为FIFO。

请使用队列解决迷宫问题 -- 我们定义一个二维数组：

int maze[5][5] = {
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0,
};
copy

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。

(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4) 
copy

• 提示：使用队列进行广度优先搜索，使用 head, tail 来表示队列的队首和队尾，使用栈来对前趋节点进行逆序输出。

重要知识点

• 队列
• 栈

参考资料

• 队列与广度优先搜索 http://learn.akae.cn/media/ch12s04.html
• 用深度优先搜索解迷宫问题 http://learn.akae.cn/media/ch12s03.html