#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];
PII q[N*N];
void bfs(int sx,int sy){
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
memset(pre,-1,sizeof pre);
int hh=0,tt=0;
q[0]={sx,sy};
while(hh<=tt){
PII c=q[hh++];
for(int i=0;i<4;i++){
int cx=c.x+dx[i],cy=c.y+dy[i];
if(g[cx][cy])continue;
if(cx<0||cx>=n||cy<0||cy>=n)continue;
if(pre[cx][cy].x!=-1)continue;
q[++tt]={cx,cy};
pre[cx][cy]={c.x,c.y};
}
}
}
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 end(0,0);
while(true){
printf("%d %d\n",end.x,end.y);
if(end.x==n-1)break;
end=pre[end.x][end.y];
}
}
最短路输出路径