AcWing 1076.迷宫问题 —— 记录路径的bfs

 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 }