求调

#include <bits/stdc++.h>

using namespace std;

struct node
{
	int ans;
	int x,y;	
};

bool operator > (node A,node B)
{
	A.ans > B.ans;
}

int dis[2010][2010];
char a[2010][2010];

void solve()
{
	int n,m;
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	
	memset(dis,0x3f,sizeof dis);
	
	priority_queue<node,vector<node>,greater<node> > q;
	q.push({0,1,1});
	dis[1][1] = 0;
	while (!q.empty())
	{
		node t = q.top();
		q.pop();
		int sum = t.ans;
		int x = t.x;
		int y = t.y;
		if (x > 1)
		{
			if (a[x - 1][y] != a[x][y])
			{
				if (dis[x - 1][y] > sum + 1)
				{
					dis[x - 1][y] = sum + 1;
					q.push({dis[x - 1][y],x - 1,y});
				} 
			} 
		} 
		if (x < n)
		{
			if (a[x + 1][y] != a[x][y])
			{
				if (dis[x + 1][y] > sum + 1)
				{
					dis[x + 1][y] = sum + 1;
					q.push({dis[x + 1][y],x + 1,y});
				} 
			} 
		} 
		if (y > 1)
		{
			if (a[x][y - 1] != a[x][y])
			{
				if (dis[x][y - 1] > sum + 1)
				{
					dis[x][y - 1] = sum + 1;
					q.push({dis[x][y - 1],x,y - 1});
				} 
			} 
		} 
		if (y < n)
		{
			if (a[x][y + 1] != a[x][y])
			{
				if (dis[x][y + 1] > sum + 1)
				{
					dis[x][y + 1] = sum + 1;
					q.push({dis[x][y + 1],x,y + 1});
				} 
			} 
		} 
	}
	
	if (dis[n][m] == 0x3f3f3f3f)
		cout << -1 << endl;
	else
	{
		cout << dis[n][m] << endl;
		
		int x = n,y = m;
		string s = "";
		while (1)
		{
			if (x == 1 && y == 1)
				break;
			if (x > 1)
			{
				if (dis[x - 1][y] + 1 == dis[x][y])
				{
					x--;
					s.push_back('D');
					continue;
				}
			}
			if (x < n)
			{
				if (dis[x + 1][y] + 1 == dis[x][y])
				{
					x++;
					s.push_back('U');
					continue;
				}
			}
			if (y > 1)
			{
				if (dis[x][y - 1] + 1 == dis[x][y])
				{
					y--;
					s.push_back('R');
					continue;
				}
			}
			if (y < n)
			{
				if (dis[x][y + 1] + 1 == dis[x][y])
				{
					y++;
					s.push_back('L');
					continue;
				}
			}
		}
		
		for (int i = s.size() - 1; i >= 0; i--)
			cout << s[i];
		cout << endl;
	}
}

int main()
{
	int t;
	cin >> t;
	
	while (t--)
		solve();
}