知识点:广度优先搜索
这个题也是一个裸的宽搜,但是明显比别的黄题宽搜难,因为它要搜索的是最小的转弯次数,别的宽搜的状态都是横纵坐标,或者再加上一个方向,再加上一个第几个走到这个点,等等,但终归都是搜索的步数,而不是转弯数,
这个题我们考虑起点,每个坐标我们也是三个数据,坐标和方向,但是题目说起始的方向任意,所以我们要遍历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)