首先正向BFS, 将通路标记为[2, 3, 4, 5,.... k], 然后从(n - 1, n - 1)编号为k的点反向找路径即可

#include <bits/stdc++.h>
using namespace std;


const int N = 1005;
int g[N][N];
vector<int> dir = {-1, 0, 1, 0, -1};

int main () {
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];       
        }
    }
    queue<pair<int, int>> q;
    q.emplace(0, 0);
    int mark = 2;
    g[0][0] = mark;
    while (!q.empty()) {
        ++mark;
        int sz = q.size();
        bool flag = false;
        for (int i = 0; i < sz; ++i) {
            auto [x, y] = q.front(); q.pop();
            if (x == n - 1 && y == n - 1) {
                flag = true;
                break;
            }
            for (int j = 0; j < 4; ++j) {
                int dx = x + dir[j], dy = y + dir[j + 1];
                if (dx < 0 || dx >= n || dy < 0 || dy >= n) continue;
                else if (g[dx][dy] != 0) continue;
                else {
                    g[dx][dy] = mark;
                    q.emplace(dx, dy);
                }
            }
        }
        if (flag) break;
    }
    // 现在把路径标记为[2...2 + x]
    vector<pair<int, int>> res; // 答案数组
    res.emplace_back(n - 1, n - 1);
    mark--;
    int x = n - 1, y = n - 1;
    while (!(x == 0 && y == 0)) {
        bool flag = false;
        for (int i = 0; i < 4; ++i) {
            int dx = x + dir[i], dy = y + dir[i + 1];
            if (dx < 0 || dx >= n || dy < 0 || dy >= n) continue;
            else if (g[dx][dy] == mark - 1) {
                mark -= 1;
                x = dx, y = dy;
                res.emplace_back(x, y);
                if (x == 0 && y == 0) {
                    flag = true;
                    break;
                } 
            }
        }
        if (flag) break;
    }
    for (int i = res.size() - 1; i >= 0; --i) {
        cout << res[i].first << ' ' << res[i].second << endl;
    }
    return 0;
}