双向BFS是从起点和终点两边扩展节点,当节点重合即为最优解。
对于双向BFS,我们逐层求解,有两个队列,当我们遍历完毕这个队列的这一层,然后就要遍历另一个队列的相同的层数。
POJ - 2243
思路
起点和终点只是一个二维坐标,因此用vis数组存储即可。从起点和终点分别维护一个队列,开始扩展,当两者重合即为最终答案。一遍过,还是有点兴奋,逐渐的会加大这种题型的难度。
1 |
|
云腾致雨,露结为霜
双向BFS是从起点和终点两边扩展节点,当节点重合即为最优解。
对于双向BFS,我们逐层求解,有两个队列,当我们遍历完毕这个队列的这一层,然后就要遍历另一个队列的相同的层数。
起点和终点只是一个二维坐标,因此用vis数组存储即可。从起点和终点分别维护一个队列,开始扩展,当两者重合即为最终答案。一遍过,还是有点兴奋,逐渐的会加大这种题型的难度。
1 | #include <iostream> |