莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 因为要正向记录路径，所以 bfs 可以反向搜
2. pre 数组不仅可以记录该点上一步状态，还能判断该点是否走过
3. 取出队头，枚举四个方向，符合条件的加入队列，并记录上一步状态
4. 最后从 (0,0) 开始还原路径

#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 1010;

int n;
int g[N][N];
PII pre[N][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});

    //初始化pre数组
    memset(pre,-1,sizeof pre);
    pre[sx][sy]={0,0};

    while(q.size())
    {
        //取出队头
        PII t=q.front();
        q.pop();

        //枚举四个方向
        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];

            //超出边界
            if(a<0||a>=n||b<0||b>=n) continue;

            //该点不可走或该点已走过
            if(g[a][b]||pre[a][b].x!=-1) continue;

            //符合条件，将该点放入队列，并记录上一步状态
            q.push({a,b});
            pre[a][b]=t;
        }
    }
}

int main()
{
    cin>>n;

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

    //从后往前bfs，因为要正向记录路径 
    bfs(n-1,n-1);

    //从(0,0)点开始还原路径
    PII end={0,0};
    while(true)
    {
        cout<<end.x<<' '<<end.y<<endl;
        if(end.x==n-1&&end.y==n-1) break;
        end=pre[end.x][end.y];
    }

    return 0;
}