迷宫问题

迷宫问题

给定一个 n×n 的二维数组,如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
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
输入样例:

1
2
3
4
5
6
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
2
3
4
5
6
7
8
9
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4

AC代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include "iostream"
#include "queue"

using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int g[N][N];
bool st[N][N];
PII memory[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()) {
PII t = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x = t.first + dx[i];
int y = t.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < n && !st[x][y] && !g[x][y]) {
q.push({x, y});
memory[x][y] = t;
st[x][y] = true;
}
}
}
}

int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &g[i][j]);
bfs();
PII t = {0, 0};
printf("%d %d\n", 0, 0);
while (t.first != n - 1 || t.second != n - 1) {
printf("%d %d\n", memory[t.first][t.second].first, memory[t.first][t.second].second);
t = memory[t.first][t.second];
}
return 0;
}

acwing 1076


迷宫问题
http://example.com/2022/05/28/迷宫问题/
作者
Charry
发布于
2022年5月28日
许可协议