题目描述
给定一个 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
C++ 代码
#include <iostream>
#include <queue>
#define x first // 这玩意可以用,没事的
#define y second
using namespace std;
const int N=1010;
typedef pair<int,int> PII;
PII path[N][N]; // 用于储存路径
bool g[N][N]; // 标记是否走过
int map[N][N],n; // 地图
int a[]={1,0,-1,0},b[]={0,-1,0,1};
void bfs()
{
queue<PII>q;
q.push({n-1,n-1}); // 往队列里插入 pair
g[n-1][n-1]=true;
while(!q.empty())
{
auto p=q.front(); // auto 会自动判断元素类型
q.pop(); // 不要忘记清除队首元素
for(int i=0;i<4;i++)
{
int xa=p.x+a[i];
int yb=p.y+b[i]; // int yb=p.x+b[i];
// 我仅仅是一个字母写错了 可悲
if(xa>=0&&xa<n&&yb>=0&&yb<n&&!g[xa][yb]&&map[xa][yb]==0)
{
q.push({xa,yb}); // 放入
g[xa][yb]=true; // 标记
path[xa][yb]=p; // 储存路径
}
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int k=0;k<n;k++)
cin>>map[i][k];
bfs();
cout<<0<<' '<<0<<endl;
int i=0,k=0;
while(i!=n-1||k!=n-1) // 其实这里没有不是仅有一种写法
{ // while(d[i][k].x!=n-1||d[i][k].y!=n-1)
cout<<path[i][k].x<<' '<<path[i][k].y<<endl;
int c=path[i][k].x; // 易错点,记清楚哦,
int d=path[i][k].y; // 已经改变的元素,不能再用
i=c;
k=d;
}
return 0;
}