#include<bits/stdc++.h> using namespace std; struct P{ int x,y,step; }; const int N=1010; int n,m,a[N][N],st[N][N],tm1[N][N]; int dx[9]={0,-1,0,1,0,-1,-1,1,1},dy[9]={0,0,1,-1,0,-1,1,-1,1}; queue<P> ps; int bfs(){ P s; s.x=1,s.y=1,s.step=0; ps.push(s); st[1][1]=1; tm1[1][1]=0; while(!ps.empty()){ int x=ps.front().x,y=ps.front().y,step=ps.front().step; ps.pop(); for(int i=1;i<=8;i++){ int tx=x+dx[i],ty=y+dy[i]; if(a[tx][ty]==0 && st[tx][ty]==0 && (tx>=1 && tx<=n) && (ty>=1 && ty<=n)) { if(tx==1 && ty==n) return step+1; P temp; temp.x=tx,temp.y=ty,temp.step=step+1; ps.push(temp); st[tx][ty]=1; tm1[tx][ty]=temp.step; } } } } int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; } } cout<<bfs()<<endl; return 0; }