首页 > 代码库 > 小结:bfs

小结:bfs

概要:我们在初始状态要到达终止状态可以沿着同深度的向下搜索,这样范围覆盖更广,在解的深度较小的时候十分适用。

技巧及注意:

bfs很多技巧啊,我来一一列举吧:

注意:存bfs状态时一定要尽量小化状态,只存有效的信息来进行bfs,而不要存整个图进去(QAQ,noip就是这样挂的。当时太弱。。)

hash判重:在一些bfs题中所有元素的范围(也可以自己映射呗)很小的情况下,我们假设有k个元吧,我们可以考虑用以基于k进制为底数的幂来进行hash,比如【wikioi】1004 四子连棋,【BZOJ】1054: [HAOI2008]移动玩具(bfs+hash),

数组判重:在一些情况下,比如纯bfs或方向限制啊什么的,可以开多维数组来记录访问状态。如:【wikioi】1026 逃跑的拉尔夫(方向判重),【BZOJ】1616: [Usaco2008 Mar]Cow Travelling游荡的奶牛(dp/-bfs)(方案判重),【BZOJ】1644: [Usaco2007 Oct]Obstacle Course 障碍训练课(bfs)(方向判重),

有障碍的距离:当出现这些起点到终点最多能越过k个障碍的图给你bfs时,可以逆着想,我们想这个点到终点需要越过的最少障碍数,然后用k来判断是否合法即可,比如:

多种约束:当约束条件增多时,我们可以考虑在bfs转移状态时维护多种信息,然后根据题意来决策,比如:【BZOJ】1632: [Usaco2007 Feb]Lilypad Pond(bfs)

绕圈约束:当bfs中要求我们绕一个指定形状(有且一个连通的)求最短距离,我们可以从这个形状边界的点射一条射线出去,然后在bfs后维护两种方向的bfs,即一种是不经过射线的,一种是从不经过射线的转移到需要经过射线的。也就是饶了一个圈过来后要绕回去时,我们就要维护后者,比如:【BZOJ】1656:[Usaco2006 Jan]The Grove 树木(bfs+特殊的技巧)

双向广搜:当遇到一种从初始状态到目标状态都给你让你求最小移动步数时,我们可以同时从初始状态和目标状态都做bfs,然后判断是否相交即可。很久以前写过一题的,不知道哪题了。。

小结:bfs