这道题就是先正着算一遍然后反着走回去

代码

#include <bits/stdc++.h>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 1010, M = N * N;int n;
int w[N][N];
PII q[M];void bfs(int xx, int yy)
{int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};int hh = 0, tt = -1;q[ ++ tt] = {xx, yy};w[xx][yy] = 2;while (hh <= tt){int x = q[hh].x, y = q[hh].y;hh ++;if (x == n && y == n) break;for (int i = 0; i < 4; i ++ ){int tx = x + dx[i], ty = y + dy[i];if (tx < 1 || tx > n || ty < 1 || ty > n) continue;if (!w[tx][ty]){q[ ++ tt] = {tx, ty};w[tx][ty] = w[x][y] + 1;}}}vector<PII> ans;hh = 0, tt = -1;q[ ++ tt] = {n, n};while (hh <= tt){int tx = q[hh].x, ty = q[hh].y;hh ++;ans.push_back({tx, ty});if (tx == 1 && ty == 1) break;for (int i = 0; i < 4; i ++ ){int x = tx + dx[i], y = ty + dy[i];if (tx < 1 || tx > n || ty < 1 || ty > n) continue;if (w[x][y] == w[tx][ty] - 1){q[ ++ tt] = {x, y};break;}}}for (int i = ans.size() - 1; i >= 0; i -- ){printf("%d %d\n", ans[i].x - 1, ans[i].y - 1);}
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )scanf("%d", &w[i][j]);//	printf("%d", bfs(1, 1));bfs(1, 1);return 0;
}