天天看点

ACM-BFS之Open the Lock——hdu1195(双向BFS)

这道题的初级版本,暴力BFS及题目详情请戳:

上回书说道,要用双向BFS来尝试一下。

终于AC了,

双向BFS,就是从两个点寻找一个共同的中间点。

然后把各自到这个中间点的步数加起来,及为最短步数。

肯定有人问了,双向BFS有啥好处捏?

鄙人,有图有真相!

单BFS:

ACM-BFS之Open the Lock——hdu1195(双向BFS)

双向BFS:

ACM-BFS之Open the Lock——hdu1195(双向BFS)

发现了不?

尤其是随着搜索广度的增大,那个范围是相当di啊!

双向BFS做法其实不难,两个队列。

一个从头开始搜,一个从尾开始搜。

但是要注意一点,要逐层搜索,不要逐点搜索呀~

要在 正向的同一层搜索完后,再去搜索反向的相应层!

什么叫逐层搜索呢?

对于这道题而言,VIS数组需要记录到达该点的步数,

对于每层搜索要把,同一步数的点全出队列遍历一遍,再进行反向搜索。

OK,这是对于这道题的双向广搜代码(感觉就是把两个广搜叠起来就OK了)