C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 960K, 提交时间: 2020-09-10 23:04:58

#include<bits/stdc++.h>
using namespace std;
char mp[505][505],hs[4]={'D','L','R','U'};
int n,m,x[4]={1,0,0,-1},y[4]={0,-1,1,0},tot=-1;
bool f[505][505];
struct node{
	int x,y,id,last;
	char f;
}ar[300000];
void print(node now){
	vector<char> v;
	while(now.id){
		v.push_back(now.f);
		now=ar[now.last];
	}
	reverse(v.begin(),v.end());
	printf("%d\n",v.size());
	for(char c: v)putchar(c);
}
void bfs(){
	queue<node> q;
	q.push(ar[++tot]={1,1,0,-1,'E'});f[1][1]=1;
	while(q.size()){
		node now=q.front();q.pop();
		for(int i=0;i<4;++i){
			int nr=now.x+x[i],nc=now.y+y[i];
			if(nr&&nc&&nr<=n&&nc<=m&&mp[nr][nc]=='0'&&!f[nr][nc]){
				ar[++tot]={nr,nc,tot,now.id,hs[i]};
				if(nr==n&&nc==m){print(ar[tot]);return;} 
				q.push(ar[tot]),f[nr][nc]=1;
			}
		}
	}
	puts("-1");
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%s",mp[i]+1);
	bfs();
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 7ms, 内存消耗: 1676K, 提交时间: 2023-03-20 16:21:53

 #include<bits/stdc++.h>
using namespace std;
const int N=550;
string s[N];
int n,m,st[N][N];
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
string a="DLRU";
struct node
{
	string s;
	int x,y,step;
};
void bfs()
{
	queue<node>q; q.push({"",0,0,0});
	st[0][0]=1;
	while(q.size())
	{
		auto temp=q.front(); q.pop();
		int x=temp.x,y=temp.y,d=temp.step;
		string ss=temp.s;
		if(x==n-1&&y==m-1)
		{
			cout<<d<<endl;
			cout<<ss;
			return ;
		}
		for(int i=0;i<4;i++)
		{
			int tempx=x+dx[i],tempy=y+dy[i];
			if(tempx<0||tempx>=n||tempy<0||tempy>=m) continue;
			if(s[tempx][tempy]=='1') continue;
			if(st[tempx][tempy]) continue;
			st[tempx][tempy]=1;
			q.push({ss+a[i],tempx,tempy,d+1});
		}
	}
}
int main(void)
{
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>s[i];
	bfs();
    if(!st[n-1][m-1]) cout<<-1;
	return 0;
}

C++ 解法, 执行用时: 35ms, 内存消耗: 50424K, 提交时间: 2021-05-27 18:56:44

#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;
char s[505][505];
int dx[4]={0,-1,1,0};
int dy[4]={1,0,0,-1};
char s2[5]={"DLRU"};
struct duqi{
	int x,y,k;
	string s1;
};
duqi q[1000005];
int b[505][505]={0};
int main()
{
	int i,j,k,l,n,m,x1,y1;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	scanf("%s",s[i]+1);
	q[0].x=1;q[0].y=1;q[0].k=0;b[1][1]=1;
	for(i=0,j=0;i<=j;i++){
		if(q[i].x==m&&q[i].y==n){
			cout<<q[i].k<<endl<<q[i].s1;return 0;
		}
		for(l=0;l<4;l++)
		{
			x1=dx[l]+q[i].x;
			y1=dy[l]+q[i].y;
			if(b[y1][x1]==0&&y1>=1&&y1<=n&&x1>=1&&x1<=m&&s[y1][x1]=='0'){
				b[y1][x1]=1;
				q[++j].y=y1;q[j].x=x1;q[j].s1=q[i].s1+s2[l];q[j].k=q[i].k+1;
			}
		}
	}
	printf("-1");
}