对于BFS,我来谈一谈自己的理解。首先,我们从一道最基础的题来进行学习:
> 洛谷B3625 迷宫寻路(仔细阅读哦,我就不解释了)
https://www.luogu.com.cn/problem/B3625#submit
> 对于这道题以及所有的BFS题目的核心,我们的思想是这样的:
直接暴力枚举每一种情况,并把其放入队列(因为队列符合BFS算法所需要的先进先出),在枚举完这一种情况的所有符合条件的衍生情况并入队后,把这一种情况出队,枚举下一个,也就是出队后的队首元素,直至找到符合条件的答案。又或者是说,枚举完了所有情况,都没有找到正确答案,在程序运行中体现这一点的是队列为空都没有找到答案的情况。
> 示例:
有一个n*m的方格,里面'#'的地方是不能走的,起点是(1,1),终点是(n,m),那么如以下图形:
.##.#
.#. . .
. . .#.
刚开始的队列(数据类型可以是pair、结构体等):
(1,1)
想要从(1,1)走到(n,m),我们可以按刚才说的流程,把(1,1)的所有衍生坐标入队,而且入队条件为该区域不为'#'且在n*m以内。
入队后的队列:
(1,1) (2,1)
为什么只有(2,1)一个呢,这是因为对于(1,1)来说,不考虑入队条件,(1,1)确实有四种衍生情况:(0,1)(2,1)(1,2)(1,0),但其中,(0,1)(1,0)超出了n*m的范围,而(1,2)则是不能通行的'#'区域,所以最终,只有(2,1)一个符合条件的坐标被加入到了队列。可到这就完了吗?不,我们在上面说过,还需要把枚举完了所有情况的(1,1)节点出队,因为它不是答案,且没有了为答案提供价值的能力。这一点在代码里的体现不太一样,在代码中,作者是把(1,1)节点先用t保存起来,再直接出队,之后再用t代替(1,1)的作用,现在,我们就完成了一次程序将要做的枚举。之后再照着这种方式继续即可求解出答案。
> 全部过程展示(队列,,一行为一次枚举):
因数据太水一条路拉通
> 代码实现:
对于程序实现上的补充:
进行一次枚举时,我们需要一个标记来表示这个路段是否走过,否则,我们的程序会在两个路段上反复横跳。