先来一道简单的迷宫模板题
迷宫由 n 行 m 列的单元格组成，每个单元格要么是空地，要么是障碍物。其中1表示空地，可以走通，2表示障碍物。输出从左上角到右下角的最短路径长度。
输入
5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 1
输出
7
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int>PII;
int n,m;
int g[1005][1005];//图
int d[1005][1005];//记录最短路径和标记是否访问过
int dx[4]={1,0,0,-1},dy[4]={0,-1,1,0};//方向数组
int ans=0;
void bfs(){
memset(d,-1,sizeof d);
d[0][0]=0;//防止在起点无限兜圈
queue<PII>qe;
qe.push({0,0});
while(qe.size()){
PII t=qe.front();
qe.pop();
for(int i=0;i<4;i++){
int nx=t.first+dx[i];
int ny=t.second+dy[i];
if(nx<0||nx>=n||ny<0||ny>m||g[nx][ny]==2||d[nx][ny]!=-1)
continue;
qe.push({nx,ny});
d[nx][ny]=d[t.first][t.second]+1;
}
}
}
int main() {
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>g[i][j];
}
}
bfs();
/*
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<d[i][j]<<" ";
}
cout<<endl;
}
*/
cout<<d[n-1][m-1];
return 0;
}
需要输出方向字符串的迷宫。
https://www.lanqiao.cn/problems/602/learning/
思路：看了csdn一位大佬的写法，可以从下往上走，再从上往回走，这样可以顺利写出走最短路的方向字符串。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int>PII;
char g[30][50];
int d[30][50];
char dir[]={'D','L','R','U'};
int dx[4]={1,0,0,-1},dy[4]={0,-1,1,0};
void bfs(){
memset(d,-1,sizeof(d));
//d[29][49]=0;
queue<PII>qe;
qe.push({29,49});
while(qe.size()){
PII t=qe.front();
qe.pop();
for(int i=0;i<4;i++){
int nx=t.first+dx[i];
int ny=t.second+dy[i];
if(nx<0||nx>=30||ny<0||ny>=50||g[nx][ny]=='1'||d[nx][ny]!=-1)continue;
qe.push({nx,ny});
d[nx][ny]=d[t.first][t.second]+1;
}
}
}
int main() {
for(int i=0;i<30;i++)cin>>g[i];
bfs();
string ans;
int x=0,y=0;
while(x!=29||y!=49){
for(int i=0;i<4;i++){
int nx=dx[i]+x;
int ny=dy[i]+y;
if(nx<0||nx>=30||ny<0||ny>=50||g[nx][ny]=='1'){
continue;
}
if(d[x][y]==d[nx][ny]+1){
ans+=dir[i];
x=nx;
y=ny;
break;
}
}
}
for(int i=0;i<30;i++){
for(int j=0;j<49;j++){
cout<<d[i][j]<<" ";
}
cout<<endl;
}
cout<<ans;
return 0;
}
标签：问题,nx,int,迷宫,bfs,ny,qe,include From： https://www.cnblogs.com/zhishikele/p/17231693.html