原题链接：https://www.acwing.com/problem/content/description/1078/
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=1010;
int n,hh,tt;
int g[N][N],dist[N][N];
PII q[N*N],pre[N][N];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
void bfs()
{
hh=0,tt=0;
q[0]={0,0};
memset(dist,-1,sizeof dist);
dist[0][0]=0;
while(hh<=tt)
{
PII t=q[hh++];
if(t.x==n-1&&t.y==n-1) return;
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(g[x][y]==1) continue;
if(dist[x][y]==-1)
{
dist[x][y]=dist[t.x][t.y]+1;
pre[x][y]={t.x,t.y};
q[++tt]={x,y};
}
}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&g[i][j]);
}
}
bfs();
int a=pre[n-1][n-1].x,b=pre[n-1][n-1].y;
vector<PII> nums;
nums.push_back({n-1,n-1});
while(a||b){
nums.push_back({a,b});
int t1=pre[a][b].x,t2=pre[a][b].y;
a=t1,b=t2;
}
nums.push_back({0,0});
for(int i=nums.size()-1;i>=0;i--)
{
printf("%d %d\n",nums[i].x,nums[i].y);
}
return 0;
}