TLE on #16

#include<bits/stdc++.h>
using namespace std;
int t;
int n,m;
bool flag=0;
int mapn[2010][2010];
int mapm[2010][2010];
int vis[2010][2010];
const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
char ch[4]={'R','L','D','U'};
struct u
{
	int a,b;
};
queue<u>Q;
string str;
int dis=0;
int ans=0;
int aa,bb;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				char ch=getchar();
				while(ch!='0'&&ch!='1')ch=getchar();
				mapn[i][j]=ch-'0';
			}
		}
		for(int i=1;i<=n;i++)
		    for(int j=1;j<=m;j++)vis[i][j]=0,mapm[i][j]=0;
		if(mapn[n][m]==mapn[n-1][m]&&mapn[n][m]==mapn[n][m-1])
		{
			cout<<-1<<endl;
			continue;
		}
		flag=0;
		vis[1][1]=1;
		Q.push((u){1,1});
		while(!Q.empty())
		{
			ans++;
			if(ans>=4000010)break;
			u hd=Q.front();
			Q.pop();
			str="";
			dis=0;
			if(hd.a==n&&hd.b==m)
			{
				flag=1;
				while(hd.a!=1||hd.b!=1)
				{
					str=ch[mapm[hd.a][hd.b]<=1?1-mapm[hd.a][hd.b]:5-mapm[hd.a][hd.b]]+str;
					aa=hd.a,bb=hd.b;
					hd.a+=dx[mapm[aa][bb]],hd.b+=dy[mapm[aa][bb]];
					dis++;
				}
				cout<<dis<<endl;
				cout<<str<<endl;
				break;
			}
			
			for(int i=0;i<4;i++)
			{
				int ax=hd.a+dx[i],ay=hd.b+dy[i];
				if(vis[ax][ay]==0&&mapn[ax][ay]!=mapn[hd.a][hd.b]&&ax>0&&ay>0&&ax<=n&&ay<=m)
				{
					vis[ax][ay]=1;
					mapm[ax][ay]=(i<=1?1-i:5-i);
					Q.push((u){ax,ay});
				}
			}
		}
		if(!flag)cout<<-1<<endl;
		while(!Q.empty())Q.pop();
	}
	return 0;
}