题目描述
给定一个 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
BFS迷宫模板
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 10;
int n, g[N][N], d[N][N];
PII q[N * N], Prev_[N][N], Path[N][N];
PII stk[N * N];
int tt_stk;
// 定义了一个数组模拟栈来逆序输出路径
void bfs()
{
int hh = 0, tt = 0;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
q[0] = {0, 0};
d[0][0] = 0;
while(hh <= tt)
{
auto t = q[hh++];
for(int i = 0; i < 4; i ++)
{
int x = t.first + dx[i], y = t.second + dy[i];
if(x >= 0 && y >= 0 && x < n && y < n && g[x][y] == 0 && d[x][y] == -1)
{
Prev_[x][y] = t;
d[x][y] = d[t.first][t.second] + 1;
q[++tt] = {x, y};
}
}
}
int x = n - 1, y = n - 1;
while( x || y )
{
auto t = Prev_[x][y];
stk[++tt_stk] = Prev_[x][y];
x = t.first, y = t.second;
}
while(tt_stk)
{
cout << stk[tt_stk].first << " " << stk[tt_stk].second << endl;
tt_stk--;
}
cout << n-1 << " " << n-1 << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
memset(d, -1, sizeof d);
for(int i = 0; i < n; i ++ )
for(int j = 0; j < n; j ++ )
cin >> g[i][j];
bfs();
return 0;
}