题目链接
洛谷 P10234 [yLCPC2024] B. 找机厅
思路分析
这题关键是找到路径。在普通 bfs 时，我们会从一个点转移到多个其它的点去，而我们只要记录下是从哪个点转移过来的即可。在这里我使用手写队列，通过结构体多开一个元素记录从哪个下标对应的点转移过来。这样找到答案时，只需要再反向退回去即可。
另外这里由于是反向，所以会在答案字符串前增加元素。推荐先加在最后得到顺序相反的字符串，再调用 reverse 函数，时间复杂度为 \(O(n^2)\)（最多可能走的点不会超过 \(n^2\) 个）。如一直加在最前面，就变成 \(O(n^3)\)，会超时。
代码呈现
#include<bits/stdc++.h>
using namespace std;
struct node{int x,y,pre;
};const int N=2010,M=4e6+10;
int t,n,m;
int mp[N][N],dx[]={1,-1,0,0},dy[]={0,0,1,-1};
bool a[N][N];
node q[M];string bfs(){ // 返回如何转移，步数即为字符串长度int head=0,tail=-1;q[++tail]={1,1,-1},mp[1][1]=0;while (head<=tail){int ux=q[head].x,uy=q[head].y;if (ux==n && uy==m){string s="";node u=q[head],v;while (u.pre!=-1){ // 逆向找答案v=q[u.pre];if (u.x-v.x==-1 && u.y-v.y==0) s+='U';else if (u.x-v.x==1 && u.y-v.y==0) s+='D';else if (u.x-v.x==0 && u.y-v.y==-1) s+='L';else s+='R';u=v;}reverse(s.begin(),s.end());return s;}for (int i=0;i<4;++i){int nx=ux+dx[i],ny=uy+dy[i];if (nx>0 && nx<=n && ny>0 && ny<=m && a[nx][ny]!=a[ux][uy] && mp[nx][ny]==-1)mp[nx][ny]=mp[ux][uy]+1,q[++tail]={nx,ny,head};}++head;}return "-1"; // 无解
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>t;while (t--){cin>>n>>m;for (int i=1;i<=n;++i){for (int j=1;j<=m;++j){char c;cin>>c;a[i][j]=(c=='1');}}memset(mp,-1,sizeof mp);string s=bfs();if (s=="-1") cout<<-1<<'\n';else cout<<s.size()<<'\n'<<s<<'\n';}return 0;
}