蓝桥杯算法提高VIP-学霸的迷宫 （C语言代码）

解题思路:

注意事项:

参考代码

#include<iostream>
#include<queue>
#include<string.h>
#define N 800
using namespace std;

int vis[N][N];
int df[4][4]={{1,0},{0,-1},{0,1},{-1,0}};	//最小字典序 {U D L R}{D L R U}
int m,n;
int map[N+2][N+2];
char dfName[4]={'D','L','R','U'};
typedef struct{
	int x,y;
	string s;
}p;
void bfs(){
	queue<p> Q;
	p cur,next;
	cur.x=1;cur.y=1;
	cur.s="";
	Q.push(cur);
	vis[1][1]=0;
	while(!Q.empty()){
		cur=Q.front();
		Q.pop();
		if(cur.x==m&&cur.y==n)	{
			cout<<cur.s.length()<<endl<<cur.s;
			break;
		}
		for(int i=0;i<4;i++){
			next.x=cur.x+df[i][0];	next.y=cur.y+df[i][1];
			if(next.x>=1&&next.x<=m&&next.y>=1&&next.y<=n&&map[next.x][next.y]==0&&vis[next.x][next.y]==-1){
					next.s=cur.s+dfName[i];
					Q.push(next);
					vis[next.x][next.y]=vis[cur.x][cur.y]+1;
			}
		}
	}
}  
int main(){
	cin>>m>>n;
	char temp;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>temp;
			map[i][j]=temp-'0';
		}
	}
	memset(vis,-1,sizeof(vis));
	bfs();
	return 0;
}