bfs总结2

· · 个人记录

说完最短路径问题，我们来看看另一种问题，最少转弯问题。

最少转弯问题，就是让你在迷宫中找到转弯次数最少的路径的转弯次数。说到这，很多人就想，诶，那是不是记录一下之前的方向，每一次看方向有没有变，变了就step+1，否则不变呢。其实这样子做并没有达到统计最少转弯路径转弯次数的目的，而是最短路径转弯次数。这时候又有很多人想，诶，那是不是，把每一个方向走到底这一行或一列上所有的点到打上标记并入队呢？到这里，大家的思路就已经正确了，可是最少转弯次数问题有一个细节非常恶心。

  1. 我们平常判断一个节点是否合法，一般是先判是否越界，再判是否有障碍物，然后判是否被标记。可是在最少转弯问题中，被标记并不能代表不能走，而是不能入队，因此如果被标记是continue而不是break。

    比如这样 B
    ↑
    C → E → D
    ↑
    A

    这里E在A走到B的时候被标记过了，但这就代表C走不到吗？显然不是，所以，遇到合法但已标记的点，只需要continue掉跳过当前点继续往前走即可。