P1649 [USACO07OCT]Obstacle Course S

知识点：广度优先搜索

这个题也是一个裸的宽搜，但是明显比别的黄题宽搜难，因为它要搜索的是最小的转弯次数，别的宽搜的状态都是横纵坐标，或者再加上一个方向，再加上一个第几个走到这个点，等等，但终归都是搜索的步数，而不是转弯数，

这个题我们考虑起点，每个坐标我们也是三个数据，坐标和方向，但是题目说起始的方向任意，所以我们要遍历4个方向，然后当前方向上，我们要把直走能走到的点都算进去，直到直走走不下去为止，因为即使这样走了很多步，这些位置加方向的转弯次数也只是0而已，所以可以说这么多位置加方向的三元组，组成了一个状态，他们的转弯次数都是0，我们广搜开始的时候要加进队列，

然后就是广搜中间的过程，我们每出列一个三元组，我们都遍历它剩下的三个方向，如果这个方向有了转弯次数，那么我们就跳过，这些个三元组遍历过了，但是如果没有，那么更新它的转弯次数，并且把它直走一直到走不下去了的都给更新入队，这里关于转向走了几步开一个数组记录，是一个小技巧

别的地方看到一句话说的挺对的，转弯次数为x的点，一定可以由某个转弯次数为x-1的点扩展而来，这应该也是这个题可以用广搜直接过掉的原因

#include <bits/stdc++.h>using namespace std;const int N = 105;struct node {int x, y, dir;node() {}node(int a, int b, int c): x(a), y(b), dir(c)