【蓝桥杯】迷宫（BFS+路径记忆）

思想：简单的BFS问题，在寻路的过程中，判断四个方向时，优先判断字典序小的方向，若满足未访问过就会优先加入队列，最后找到的路，即为字典序最小。
这里我们在node节点中，引入变量s，用来记录到这个节点时，所有的方向序列。

#include<iostream>
#include<queue>

using namespace std;

struct node{
	int x;
	int y;
	string s;  //用于保存到当前节点的所有方向步
	node(int xx,int yy,string ss){
		x = xx;
		y = yy;
		s = ss;
	}
};

int tab[40][60] = {0};

int vis[40][60] = {0};

int dir[4][2] = {{1,0},{0,-1},{0,1},{-1,0}}; //按字典序，由小到大排的。

char dic[4] = {'D','L','R','U'};//对应上面四个方向

int main(){
	queue<node>qu;
	string s;
	for(int i = 1;i <= 30;i++){
		cin>>s;
		for(int j = 0;j < s.length();j++){
			tab[i][j + 1] = s[j] - '0';
		}
	}
	qu.push(node(1,1,""));
	while(!qu.empty()){
		node tn = qu.front();
		qu.pop();
		vis[tn.x][tn.y] = 1;
		for(int i = 0;i < 4;i++){
			int x = tn.x + dir[i][0];
			int y = tn.y + dir[i][1];
			if( x == 30 && y == 50){
				for(int j = 0;j < tn.s.length();j++){
					cout<<tn.s[j];
				}
				cout<<dic[i];
				return 0;
			}
			if(!tab[x][y] && !vis[x][y] && x >= 1 && x <= 30 && y >= 1 && y <= 50){
				qu.push(node(x,y,tn.s + dic[i]));
			}
		}
	}
	return 0;
}

结果:
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR