迷宫问题
给定一个 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
算法1
BFS
C++ 代码
#include <queue>
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair <int ,int> PII;
const int N=1010;
int g[N][N];
PII memory[N][N];
int st[N][N];
int n;
void BFS(){
queue<PII>q;
q.push({n-1,n-1});
st[n-1][n-1]=true;
int dx[]={0,-1,0,1},dy[]={-1,0,1,0};
while(q.size()){
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i ++){
int x=dx[i]+t.x,y=dy[i]+t.y;
if(x < 0 || x >= n || y < 0 || y >= n) continue;
if(st[x][y]) continue;
if(g[x][y] == 1) continue;
q.push({x,y});
st[x][y] = true;
memory[x][y] = t;
}
}
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++){
for(int j = 0;j < n; j ++){
cin >> g[i][j];
}
}
BFS();
PII end = {0,0};
cout << 0 << ' ' << 0 << endl;
while(end.x != n-1 || end.y != n-1){
cout << memory[end.x][end.y].x << ' ' << memory[end.x][end.y].y << endl;
int x = end.x, y= end.y;
end.x = memory[x][y].x, end.y = memory[x][y].y;
}
return 0;
}