标签：preview queue turn type element front 编程 转移 pac
给定一个 n×nn×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)(0,0)，右下角坐标为 (n?1,n?1)。
数据范围
0≤n≤1000
1 #include 2 #include 3 #include 4 #include
5 #include 6
7 #define x first
8 #define y second
9
10 using namespace std;
11
12 typedef pairint, int> PII;
13
14 const int N = 1010;
15 int g[N][N];
16 PII pre[N][N];
17 int n;
18
19 void bfs()
20 {
21 int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
22 queue q;
23 q.push({n - 1, n - 1});
24 pre[n - 1][n - 1] = {-1, -1};
25
26 while (q.size())
27 {
28 PII t = q.front();
29 q.pop();
30
31 for (int i = 0; i 4; i ++ )
32 {
33 int x = t.x + dx[i], y = t.y + dy[i];
34 if (x 0 || x >= n || y 0 || y >= n) continue;
35 if (g[x][y] == 1) continue;
36 if (pre[x][y].x != 0 || pre[x][y].y != 0) continue;
37
38 pre[x][y] = t;
39 if (x == 0 && y == 0) return;
40 q.push({x, y});
41 }
42 }
43 }
44
45 int main()
46 {
47 scanf("%d", &n);
48 for (int i = 0; i )
49 for (int j = 0; j "%d", &g[i][j]);
50
51 bfs();
52
53 PII end = {0, 0};
54
55 while (1)
56 {
57 printf("%d %d\n", end.x, end.y);
58 if (end.x == n - 1 && end.y == n - 1) break;
59 end = pre[end.x][end.y];
60 }
61
62 return 0;
63 }
记录路径只需使用一个pre数组用来记录当前状态是从那个状态转移过来即可。
AcWing 1076.迷宫问题 —— 记录路径的bfs
标签：preview queue turn type element front 编程 转移 pac
原文地址：https://www.cnblogs.com/HYfeng-yanwu/p/14314301.html