找机厅 洛谷 BFS

P10234 [yLCPC2024] B. 找机厅 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fr first
#define sc second
using namespace std;
string maze[2000];
int vis[2000][2000];
char dirs[2005][2005];
string s="URDL";
int n,m;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
pii parent[2000][2000];
bool check(int x,int y)
{return x>=0&&x<n&&y>=0&&y<m;
}
bool bfs(int x,int y)
{for(int i=0;i<n;i++)for(int j=0;j<m;j++){vis[i][j]=0;parent[i][j]={-1,-1};dirs[i][j]=' ';}queue<pii>q;q.push({0,0});vis[0][0]=1;while(!q.empty()){pii now=q.front();if(now.fr==n-1&&now.sc==m-1)return true;q.pop();for(int i=0;i<4;i++){int nx,ny;nx=now.first+dir[i][0];ny=now.second+dir[i][1];if(check(nx,ny)&&!vis[nx][ny]){if(maze[nx][ny]==maze[now.fr][now.sc])continue;q.push({nx,ny});vis[nx][ny]=vis[now.fr][now.sc]+1;parent[nx][ny]=now;dirs[nx][ny]=s[i];}}}return false;
}
void dfs(int x,int y)
{if(!x&&!y)return;dfs(parent[x][y].fr,parent[x][y].sc);cout<<dirs[x][y];
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){cin>>n>>m;for(int i=0;i<n;i++)cin>>maze[i];if(bfs(0,0)){cout<<vis[n-1][m-1]-1<<'\n';dfs(n-1,m-1);cout<<'\n';}else cout<<"-1\n";}return 0;
}

刚开始我是没想到怎么打印出路径的，但是题解几乎搜不到，所以只能问了文心一言，结果她终于有用了一回，她让我弄个数组记录父节点，再弄个数组记录路径，然后直接DFS。跟着改了下，结果没想到真的AC了。

不开新的数组也可以，从最后的节点开始再来一次BFS，然后把路径存起来再反向输出，我试试。

是可以的，再用一遍bfs。但是代码比存父节点再用dfs稍微长一点，但是这些东西都是一样的。

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fr first
#define sc second
using namespace std;
string mz[2000];
int vis[2000][2000];
string s="DLUR";
int n,m;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool check(int x,int y)
{return x>=0&&x<n&&y>=0&&y<m;
}
bool bfs(int x,int y)
{for(int i=0;i<n;i++)for(int j=0;j<m;j++)vis[i][j]=0;queue<pii>q;q.push({0,0});vis[0][0]=1;while(!q.empty()){pii now=q.front();if(now.fr==n-1&&now.sc==m-1)return true;q.pop();for(int i=0;i<4;i++){int nx,ny;nx=now.first+dir[i][0];ny=now.second+dir[i][1];if(check(nx,ny)&&!vis[nx][ny]){if(mz[nx][ny]==mz[now.fr][now.sc])continue;q.push({nx,ny});vis[nx][ny]=vis[now.fr][now.sc]+1;}}}return false;
}
void sfb(int x,int y)
{string ans;queue<pii>q;q.push({x,y});while(!q.empty()){pii now=q.front();q.pop();for(int i=0;i<4;i++){int nx,ny;nx=now.fr+dir[i][0];ny=now.sc+dir[i][1];if(check(nx,ny)&&mz[nx][ny]!=mz[now.fr][now.sc]){if(vis[nx][ny]==vis[now.fr][now.sc]-1){ans+=s[i];q.push({nx,ny});break;}}}}reverse(ans.begin(),ans.end());cout<<ans<<'\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){cin>>n>>m;for(int i=0;i<n;i++)cin>>mz[i];if(bfs(0,0)){cout<<vis[n-1][m-1]-1<<'\n';sfb(n-1,m-1);cout<<'\n';}else cout<<"-1\n";}return 0;
}

加油，嘻嘻。感觉这题还算简单的。