RT

https://www.luogu.com.cn/record/150006935

https://www.luogu.com.cn/record/150185760

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
typedef long long ll;
int n,m;
int tim[N][N];
bool flag;
char a[N][N];
bool vis[N][N];
int xy[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
char dir[4] = {'L','R','D','U'};
void print(int x,int y){
	for(int i=0;i<4;i++){
		int nx = x + xy[i][0],ny = y + xy[i][1];
		if(tim[x][y] == tim[nx][ny] + 1 && a[x][y] != a[nx][ny] && nx >= 1 && nx <= n && ny >= 1 && ny <= m){
			print(nx,ny);
			cout<<dir[i];
			break;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
			}
		}
		memset(vis,false,sizeof(vis));
		memset(tim,0,sizeof(tim));
		flag = false;
		string s;
		queue<pair<int,int> > q;
		q.push({1,1});
		vis[1][1] = true;
		while(!q.empty()){
			int x = q.front().first,y = q.front().second;
			q.pop();
			for(int i=0;i<4;i++){
				int nx = x + xy[i][0],ny = y + xy[i][1];
				if(!vis[nx][ny] && a[nx][ny] != a[x][y] && nx >= 1 && nx <= n && ny >= 1 && ny <= m){
					vis[nx][ny] = true;
					q.push(make_pair(nx,ny));
					tim[nx][ny] = tim[x][y] + 1;
				}
			}
		}
		
		if(vis[n][m]){
			cout<<tim[n][m]<<'\n';
			print(n,m);
			cout<<'\n';
		}else{
			cout<<-1<<'\n';
		}
	}
	return 0;
}