我们在进行bfs的时候会将所有可能到达的点遍历并入队，但是我们只想要到达终点的那一条路径
易知到达终点的路径只有一条，但是我们每次存的是当前点是由那个点转移过来的，如果正着搜
不能输出从开始到结尾的路径，而且输出的路径也不一定对(到达终点的路径才是唯一的，从起点走的不一定唯一)
所以要倒着搜。

综上所述，倒着搜的原因一共有两点：
1、方便我们正着输出路径
2、从起点开始遍历的路径唯一

#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second

const int N = 1010;
int g[N][N];
bool st[N][N];
PII pre[N][N];
int n;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void bfs(int sx,int sy)
{
    queue<PII>q;
    q.push({sx,sy});
    st[sx][sy] = true;
    while(!q.empty())
    {
        PII t = q.front();
        q.pop();
        for(int i = 0; i < 4; i ++)
        {
            int x = t.x + dx[i],y = t.y + dy[i];
            if(x < 0 || x >= n || y < 0 || y >= n)continue;
            if(st[x][y])continue;
            if(g[x][y] == 1)continue;
            pre[x][y] = {t.x,t.y};
            q.push({x,y});
            st[x][y] = true;
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    for(int j = 0; j < n; j ++)
    cin >> g[i][j];

    bfs(n - 1,n - 1);

    PII ed = {0,0};
    while(1)
    {
        printf("%d %d\n",ed.x,ed.y);
        if(ed == make_pair(n - 1,n - 1))break;
        ed = pre[ed.x][ed.y];
    }
    return 0;
}