蓝桥杯算法提高VIP-学霸的迷宫 （C++代码）耿直的BFS搜索，注意字典序

解题思路:
    利用结构体构建节点，其包含数据x,y位置，step走过的步数，way走过的方向存储。

    我这一套方法优化程度很低，但是相当好理解。

    利用BFS逐个进行搜索，这里需要记住的一点是搜索的顺序必须要按照DLRU这样的字典序进行排列，否则的话会产生一些错误数据。

    别忘了使用vis做地图标记，否则的话分分钟爆时。

参考代码:

#include<bits/stdc++.h>
#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int maxn=1005;
/*
int dir[4][2]= {0,1,0,-1,1,0,-1,0};
//右，左，下，上，四个方向
这样子用方向会错，原因是需要写字典序最小的 
*/
int dir[4][2]={1,0,0,-1,0,1,-1,0};
//按照DLRU的字典序进行排列 
int vis[maxn][maxn];	//mark map
char mp[maxn][maxn];	//map array

int n,m;

struct state {
	int x,y;
	int step;
	string way;
};
state ans;	//答案变量

bool check(state s){
	if(!vis[s.x][s.y]&&s.x<n&&s.x>=0&&s.y<m&&s.y>=0){
		return true;
	}
	return false;
}

bool bfs() {
	queue<state> q;
	state now,next,st;
	st.x=0,st.y=0,st.step=0,st.way="";
	q.push(st);
	vis[st.x][st.y]=1;
	while(!q.empty()) {
		now=q.front();
		if(now.x==n-1&&now.y==m-1) {
			ans.x=now.x;
			ans.y=now.y;
			ans.step=now.step;
			ans.way=now.way;
			return true;
		}
		for(int i=0; i<4; i++) {
			next.x=now.x+dir[i][0];
			next.y=now.y+dir[i][1];
			next.step=now.step+1;
			switch(i) {
				case 0:
					next.way=now.way+"D";
					break;
				case 1:
					next.way=now.way+"L";
					break;
				case 2:
					next.way=now.way+"R";
					break;
				case 3:
					next.way=now.way+"U";
					break;
			}
			if(check(next)){
				q.push(next);
				vis[next.x][next.y]=1;
			}
		}
		q.pop();
	}
	return false;
}


int main() {
	hh;
	cin>>n>>m;
	memset(vis,0,sizeof(vis));
	memset(mp,0,sizeof(mp));
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cin>>mp[i][j];
			if(mp[i][j]=='1') {
				vis[i][j]=1;
			}
		}
	}
	if(bfs()){
		cout<<ans.step<<endl;
		cout<<ans.way<<endl;
	}else{
		cout<<'0'<<endl;
	}
	return 0;
}