UKE求助

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e3+5;
int T,n,m,f[N][N],dx[]={0,1,0,-1},dy[]={1,0,-1,0};
char cc[N][N],o[]={'U','R',' ','L','D'};
queue<pair<int,int> > q;
pair<int,int> u;
struct P{
	int fx,fy;
}fa[N][N];
inline int rd(){
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
bool check(int a,int b,int c,int d){return (a+c>0&&a+c<=n&&b+d>0&&b+d<=m&&f[a][b]+1<f[a+c][b+d]&&cc[a+c][b+d]!=cc[a][b]?1:0);}
void bfs(){
	int x,y;
	while(q.empty()==0&&f[n][m]>4e6+7){
		u=q.front();q.pop();
		x=u.first,y=u.second;
		for(int i=0;i<4;++i) if(check(x,y,dx[i],dy[i])){
		f[x+dx[i]][y+dy[i]]=f[x][y]+1;
		fa[x+dx[i]][y+dy[i]].fx=x,fa[x+dx[i]][y+dy[i]].fy=y;
        q.push({x+dx[i],y+dy[i]});
	    }
	}
	
}
void find(int x,int y){
	if(fa[x][y].fx!=1||fa[x][y].fy!=1) find(fa[x][y].fx,fa[x][y].fy);
	cout<<o[2+2*(fa[x][y].fx-x)+fa[x][y].fy-y];
}
signed main(){
	T=rd();
	while(T--){
		n=rd();m=rd();
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
			    cin>>cc[i][j],f[i][j]=40000000;
		while(!q.empty()) q.pop();
		f[1][1]=0;
		q.push({1,1});
		bfs();
		if(f[n][m]>4e6+7) cout<<"-1"<<'\n';
		else{
			cout<<f[n][m]<<'\n';
			find(n,m);cout<<'\n';
		}
	}
	return 0;
}