这道题的初级版本,暴力BFS及题目详情请戳:
上回书说道,要用双向BFS来尝试一下。
终于AC了,
双向BFS,就是从两个点寻找一个共同的中间点。
然后把各自到这个中间点的步数加起来,及为最短步数。
肯定有人问了,双向BFS有啥好处捏?
鄙人,有图有真相!
单BFS:
双向BFS:
发现了不?
尤其是随着搜索广度的增大,那个范围是相当di啊!
双向BFS做法其实不难,两个队列。
一个从头开始搜,一个从尾开始搜。
但是要注意一点,要逐层搜索,不要逐点搜索呀~
要在 正向的同一层搜索完后,再去搜索反向的相应层!
什么叫逐层搜索呢?
对于这道题而言,VIS数组需要记录到达该点的步数,
对于每层搜索要把,同一步数的点全出队列遍历一遍,再进行反向搜索。
OK,这是对于这道题的双向广搜代码(感觉就是把两个广搜叠起来就OK了)