MMM_JiaoFu悬关

#include<bits/stdc++.h>
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

const int maxn=4000010;

char b[2005][2003];
int up[4000005];
int n,m;
vector<pair<int,int> > g[maxn];
void add_edge(int s,int e,int d) 
{
	g[s].push_back(make_pair(e,d));
}
int dist[maxn];
bool done[maxn];
void dijkstra(int ss)
{
	memset(dist,0x3f,sizeof(dist));
	memset(done,0,sizeof(done));
	dist[ss] = 0;
	priority_queue<pair<int,int> > heap;
	heap.push(make_pair(0,ss));
	for (;heap.size();)
	{
		while (done[heap.top().second])
			heap.pop();
		int p = heap.top().second;
		heap.pop();
		done[p] = true;
		for (int j=0;j<g[p].size();j++)
		{
			int q=g[p][j].first;
			int d=g[p][j].second;
			if (dist[q] > dist[p] + d)
			{
				dist[q] = dist[p] + d;
				up[q]=p;
				heap.push(make_pair(-dist[q],q));
			}
		} 
	}
}
void dfs(int x){
	if(x==1) return;
	dfs(up[x]);
	//x=(i-1)*m+j
	//printf("%lld\n",x);
	int tt=x%m;
	if(tt==0) tt=m;
	//x=x-tt  /m +1
	int ttt=(x-tt)/m+1;
	int bb=up[x]%m;
	if(bb==0) bb=m;
	int bbb=(up[x]-bb)/m+1;
	if(bb>tt) printf("U");
	else if(bb<tt) printf("D");
	if(bbb>ttt) printf("L");
	else if(bbb<ttt) printf("R");
}
int main()
{
	int t;
	cin>>t;
	while(t--){
		scanf("%d%d",&n,&m);int d;int ss;
//		for (int i=1;i<=n;i++){
//			for (int j=1;j<=m;j++){
//				b[i][j]=0;
//			}
//		}
		for (int i=1;i<=n;i++){
			for (int j=1;j<=m;j++){
				b[i][j]=' ';
				for(;b[i][j]!='0' && b[i][j]!='1';)
				scanf("%d",&b[i][j]);
			}
		}
		for (int i=1;i<=n;i++){
			for (int j=1;j<=m;j++){
				if(b[i][j]!=b[i-1][j]&&b[i-1][j]>40&&i-1>=1&&i-1<=n&&j>=1&&j<=m){
					add_edge((i-1)*m+j,(i-2)*m+j,1);
				}
				if(b[i][j]!=b[i+1][j]&&b[i+1][j]>40&&i+1>=1&&i+1<=n&&j>=1&&j<=m){
					add_edge((i-1)*m+j,(i)*m+j,1);
				}	
				if(b[i][j]!=b[i][j-1]&&b[i][j-1]>40&&i>=1&&i<=n&&j-1>=1&&j-1<=m){
					add_edge((i-1)*m+j,(i-1)*m+j-1,1);
				}
				if(b[i][j]!=b[i][j+1]&&b[i][j+1]>40&&i>=1&&i<=n&&j+1>=1&&j+1<=m){
					add_edge((i-1)*m+j,(i-1)*m+j+1,1);
				}	
			}
		}
		dijkstra(1);
		for (int i=1;i<=n*m;i++){
			g[i].clear();
		}
		if(done[n*m]==false){
			printf("-1\n");
			continue;
		}
		printf("%d\n",dist[n*m]);
		dfs(n*m);
		printf("\n");
		
	}
	return 0;
}