pre 数组标记一下走过的前一个节点
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e3+10;
int a[N][N],vis[N][N],step[N][N],pre[N*N];
int d[4][2] = {0,1,0,-1,1,0,-1,0};
int n;
int id(int x,int y)
{
return x*n + y;
}
int main()
{
memset(pre,-1,sizeof pre);
cin >> n;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
scanf("%d",&a[i][j]);
queue<PII> q;
q.push({0,0});vis[0][0] = 1;
while(q.size())
{
PII fa = q.front(); q.pop();
for(int i = 0; i < 4; ++i)
{
int x = fa.first + d[i][0], y = fa.second + d[i][1];
if(0<=x&&x<n&&0<=y&&y<n&&!a[x][y]&&!vis[x][y])
{
pre[id(x,y)] = id(fa.first,fa.second);
q.push({x,y}); vis[x][y] = 1;
}
}
}
int t = id(n-1,n-1);
vector<int> v;
while(t != -1)
{
v.push_back(t);
t = pre[t];
}
reverse(v.begin(),v.end());
for(auto x:v) printf("%d %d\n",x/n,x%n);
return 0;
}