AcWing算法提高课【第二章搜索】最短路模型

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 typedef pair<int, int> PII;
 8 
 9 #define x first
10 #define y second
11 
12 const int N = 1010;
13 
14 int n;
15 int g[N][N];
16 PII q[N * N];
17 PII pre[N][N];
18 
19 void bfs(int sx, int sy)
20 {
21     memset(pre, -1, sizeof pre);
22     int tt = 0, hh = 0;
23     q[0] = {sx, sy};
24     pre[sx][sy] = {0, 0};
25     
26     int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
27     while (hh <= tt)
28     {
29         PII t = q[hh ++ ];
30         for (int i = 0; i < 4; i ++ )
31         {
32             int x = t.x + dx[i], y = t.y + dy[i];
33         
34             if (x < 0 || x >= n || y < 0 || y >= n) continue;
35             if (g[x][y]) continue;
36             if (pre[x][y].x != -1) continue;
37             
38             pre[x][y] = {t.x, t.y};
39             q[++ tt] = {x, y};
40         }
41     }
42 }
43 int main()
44 {
45     scanf("%d", &n);
46     for (int i = 0; i < n; i ++ ) 
47         for (int j = 0; j < n; j ++ ) 
48             scanf("%d", &g[i][j]);
49             
50     bfs(n - 1, n - 1);
51     
52     PII end(0, 0);
53     while (true)
54     {
55         printf("%d %d\n", end.x, end.y);
56         if (end.x == n - 1 && end.y == n - 1) break;
57         end = pre[end.x][end.y];
58     }
59     return 0;
60 }