思路：bfs+标记每个点从哪来，然后递归出路径

重点在 opt() 里 QWQ怎么肥四

#include <iostream>
#include <cstring>
using namespace std;
const int N=2e3+5,inf=0x3f3f3f3f;
struct nd{int x,y;}q[N*N],pre[N][N];
int t,n,m;
char s[N][N];
int l,r;
int dist[N][N],vis[N][N];
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
const int pt[4]={'U','D','L','R'};

void bfs(){
    for(int i=0; i<=n+1; i++) for(int j=0; j<=m+1; j++) vis[i][j]=0,dist[i][j]=inf;
    q[l=r=1]={1,1};
    dist[1][1]=0,vis[1][1]=1;
    while(l<=r){
        int x=q[l].x,y=q[l].y; l++;
        // printf("%d %d\n",x,y);
        for(int i=0; i<4; i++){
            int fx=x+dx[i],fy=y+dy[i];
            if(vis[fx][fy] || s[fx][fy]==s[x][y]
                || fx<1 || fy<1 || fx>n || fy>m) continue;
            // printf("dist[%d][%d]=%d   dist[%d][%d]=%d\n",fx,fy,dist[fx][fy],x,y,dist[x][y]);
            vis[fx][fy]=1;
            dist[fx][fy]=dist[x][y]+1;
            pre[fx][fy]={x,y};
            q[++r]={fx,fy};
        }
    }
}

void opt(int x,int y,int tx,int ty){
    // 这一行在前面的话 AC，但是样例 RD -> DR
    // 在后面的话样例过了，但是 #1 就 WA
    if(x!=1 || y!=1) opt(pre[x][y].x,pre[x][y].y,x,y);
    
    for(int i=0; i<4; i++)
        if(x+dx[i]==tx && y+dy[i]==ty){
            printf("%c",pt[i]);
            break;
        }
}

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++) scanf("%s",s[i]+1);
        bfs();
        if(dist[n][m]==inf) puts("-1");
        else printf("%d\n",dist[n][m]),opt(pre[n][m].x,pre[n][m].y,n,m),puts("");
    }
    return 0;
}