迷宫问题
题目 迷宫问题
给定一个 n×n 的二维数组，如下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
数据保证至少存在一条从左上角走到右下角的路径。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含 n 个整数 0 或 1，表示迷宫。
输出格式 输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。
按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)，右下角坐标为 (n−1,n−1)。
数据范围
0≤n≤1000
输入样例：
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4
思路分析
模版基础上加个p[] 与4个拓展坐标一一对应
达到终点的时候 做一次dfs回溯路径
pre记录的是这个点被上个点往哪个方向转移而来
所以从当前点找回上一个点 应该与URDL逻辑相反
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=1010;
int g[N][N],d[N][N];
char pre[N][N];
int n;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
char p[4]={'U','R','D','L'};
bool isVaild(int x,int y){
return x>=0 && x<=n-1 && y>=0 && y<=n-1 && d[x][y]==-1;
}
void print_path(int x,int y){
if(x<0 || y<0) return;
if(pre[x][y]=='U')
print_path(x+1,y);
if(pre[x][y]=='R')
print_path(x,y-1);
if(pre[x][y]=='D')
print_path(x-1,y);
if(pre[x][y]=='L')
print_path(x,y+1);
cout<<x<<" "<<y<<endl;
}
void bfs(int x,int y){
queue<PII> q;
memset(d,-1,sizeof d);
q.push({x,y});
d[x][y]=0;
while(!q.empty()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
if(ux==n-1 && uy==n-1){
print_path(ux,uy);
return;
}
for(int i=0;i<4;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny) && g[nx][ny]==0){
q.push({nx,ny});
d[nx][ny]=d[ux][uy]+1;
pre[nx][ny]=p[i];
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>g[i][j];
}
}
bfs(0,0);
return 0;
}
💬 评论