2019年蓝桥杯省赛-迷宫

题目

题目链接

题解

BFS。

BFS模板，但是我做错了。

我的做法是将到达终点的全部路径都加入到一个vector中，最后对vector排序，输出第一个字符串即可。

但是这样做是错误的，准确的说是不一定对。

正确的做法是对于每一个位置都按照“DLRU”的顺序遍历，因为DLRU的字典序最小，先遍历字典序小的方向，只要到达终点，那么一定就是字典序最小的路径。

为什么我的做法不对呢？

对于这个上下对称的两条道路而言，到达终点的总步数是相同的，要求字典序最小，那么肯定选下面的路径，因为下面的路径在两条路分叉的时候是D，而上面的路径是U，D字典序小于U，所以选下面的。即选择下面这条路是最终答案。

我们来模拟一下如果采用我的做法（按照上下左右的顺序遍历，最后对全部到达终点的路径排序）的结果。

采用BFS，会先遍历灰色点的四个方向，而遍历红色点的四个方向。在遍历灰色点位置的四个方向时，上：不可回头；下：即紫色点，没走过，加入队列，标记为1；左右：撞墙，不行。灰色点的四个方向遍历完成，再遍历红色点的四个方向，上：被标记，不行；下：不可回头；左右：撞墙，不行。红色点不可扩展了，所以最终的路径中也不可能存在由红色点到达的路径了，也就是说我的方法找不到正确路径。

道理很明显，遍历灰色点四个方向时走过了紫色点，导致红色点不能再走紫色点，故红色点无法到达终点，也就没有我们需要的答案。

这提醒我们，一般来说队列实现的基础的BFS只能计算最短路径长度，在处理其他特殊要求的题目时一定要注意考虑这种特殊情况。

代码

#include
using namespace std;

#define PII pair

const int N = 30, M = 50;

queue  q;
vector  v;
string mp[N];
int dir[2][4] = {1, 0, 0, -1, 0, -1, 1, 0};

bool cmp (string s1, string s2) {
	return s1