$$\color{Purple}{kuangbin题解目录}$$
描述
给定一个 $n \\times 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 \\le n \\le 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
思路
基于bfs的思想,这题主要考察的是输出路径,可采取递归实现路径的输出,用$xx$数组记录当前点的前驱结点的横坐标,用$yy$数组记录当前点的前驱结点的纵坐标,此题我下标是从(1,1)开始的,输出时坐标应为$(x-1,y-1)$.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#define MAXN 1010
using namespace std;
int n;
int g[MAXN][MAXN];
int xx[MAXN][MAXN],yy[MAXN][MAXN];
int vis[MAXN][MAXN];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
struct node{
int x;
int y;
int step;
};
int bfs()
{
queue<node> q;
q.push({1,1,0});
vis[1][1]=1;
while(q.size()>0)
{
node temp=q.front();
q.pop();
if(temp.x==n&&temp.y==n)
return temp.step;
for(int i=0;i<=3;i++)
{
int dx=temp.x+dir[i][0],dy=temp.y+dir[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=n&&vis[dx][dy]==0&&g[dx][dy]==0)
{
//cout << dx << " " << dy << endl;
vis[dx][dy]=1;
q.push({dx,dy,temp.step+1});
xx[dx][dy]=temp.x;
yy[dx][dy]=temp.y;
}
}
}
return -1;
}
void pre_out(int x,int y)
{
if(x!=1||y!=1)
{
pre_out(xx[x][y],yy[x][y]);
printf("%d %d\n",x-1,y-1);
return ;
}
printf("0 0\n");
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&g[i][j]);
int res=bfs();
//cout << res << endl;
pre_out(n,n);
return 0;
}