P10234

WA求调

#include<bits/stdc++.h>
using namespace std;
int T,n,m,x,y,a[1145][1145],lst[1145*1145][2],len,dis[1145][1145],pre[1145][1145][2],kd[][2]= {1,0,-1,0,0,1,0,-1};
void print (int x,int y) {
	if(x==1 && y==1) return;
	int prex=pre[x][y][0],prey=pre[x][y][1];
	print(prex,prey);
	if(prex-1==x)cout<<'U';
	if(prex+1==x)cout<<'D';
	if(prey-1==y)cout<<'L';
	if(prey+1==y)cout<<'R';
}
int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--) {
		cin>>n>>m;
		x=1;
		y=1;
		fill(dis[0],dis[max(n,m)+10],0);
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=m; j++) {
				char c;
				cin>>c;
				a[i][j]= (c=='1');
			}
		}
		len=1;
		lst[len][0]=lst[len][1]=dis[1][1]=1;
		for(int i=1; i<=len; i++) {
			int xx=lst[i][0],yy=lst[i][1];
			for(int j=0; j<=3; j++) {
				int dx=xx+kd[j][0],dy=yy+kd[j][1];
				if(dx>=1&&dy<=n&&dy>=1&&dy<=m&&a[xx][yy]!=a[dx][dy]&&dis[dx][dy]==0) {
					lst[++len][0]=dx,lst[len][1]=dy;
					dis[dx][dy]=dis[xx][yy]+1;
					pre[dx][dy][0]=xx;
					pre[dx][dy][1]=yy;
				}
			}
		}
		if(!dis[n][m]) {
			cout<<-1<<endl;
		} else {
			cout<<dis[n][m]-1<<endl;
			print(n,m);
			cout<<endl;
		}
	}
	return 0;
}