0迷宫 - 蓝桥云课 (lanqiao.cn)
思路 :
最后一定要倒数输出路径,因为从前面输出你会找不到下一个到底是谁,bfs过程是找最小路径,最后输出是去找方向,但是此题作为一个填空题,我直接手写(开玩笑)
AC代码:
#include<iostream>
#include<queue>
#include<utility>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
char g[30][50];
int d[30][50],pre[40][60];
int ans = 0;
int dx[4] = {1,0,0,-1},dy[4] = {0,-1,1,0};
char dir[4] = { 'D','L','R','U' };
void bfs(int x,int y)
{
queue<PII> q;
q.push({x,y});
memset(d,-1,sizeof d);
d[0][0] = 0;
while(q.size())
{
auto t = q.front();
q.pop();
for(int i=0;i<4;i++)
{
int a = t.first + dx[i],b = t.second + dy[i];
if(a >= 0 && a < 30 && b >= 0 && b < 50 && g[a][b] == '0' && d[a][b] == -1)
{
d[a][b] = d[t.first][t.second] + 1;
pre[a][b] = i;
q.push({a,b});
}
}
}
return;
}
int main()
{
// 请在此输入您的代码
for(int i=0;i<30;i++)
{
for(int j=0;j<50;j++)
{
cin >> g[i][j];
}
}
bfs(0,0);
int x = 29,y = 49;
vector<int> v;
while(x!=0 || y != 0)
{
int temp = pre[x][y];
v.push_back(temp);
x -= dx[temp],y -= dy[temp];
}
for(int i=v.size()-1;i>=0;i--) cout << dir[v[i]];
return 0;
}