定义一个二维数组：
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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
1
2
3
4
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
|
Sample Output
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)
|
代码
c99中不能{ x, y }要make_pair(x, y)
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
typedef pair<int, int> PII;
const int N = 10;
int g[N][N];
bool vis[N][N];
PII pre[N][N];
void bfs()
{
queue<PII> q;
q.push({ 0, 0 });
vis[0][0] = true;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while (q.size())
{
PII k = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int x = k.first + dx[i], y = k.second + dy[i];
if(x >= 0 && x < 5 && y >= 0 && y < 5 && g[x][y] == 0 && !vis[x][y])
{
vis[x][y] = true;
pre[x][y] = k;
q.push({ x, y });
}
}
}
}
int main()
{
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
scanf("%d", &g[i][j]);
bfs();
pre[0][0] = { -1, -1 };
stack<PII> s;
s.push({ 4, 4 });
PII Pre = pre[4][4];
while (Pre.first != -1 && Pre.second != -1)
{
s.push(Pre);
Pre = pre[Pre.first][Pre.second];
}
while (!s.empty())
{
printf("(%d, %d)\n", s.top().first, s.top().second);
s.pop();
}
return 0;
}
|
