#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cstdlib>
using namespace std;
int n;
int a[5100][5100];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int vis[5100][5100];
struct node
{
    int x,y,dis;
    node(){}
    node(int xx,int yy,int ddis):x(xx),y(yy),dis(ddis){}
};
vector<node> ve;
int bfs()
{
    queue<node> q0,q1;
    ve.clear();
    q0.push(node(0,0,0));
    vis[0][0]=1;
    while(1)
    {
        bool judge=false;
        while(!q0.empty())
        {
            judge=true;
            node z=q0.front();q0.pop();
            if(z.x==n-1&&z.y==n-1) return z.dis;
            for(int i=0;i<4;i++)
            {
                int nx=z.x+dir[i][0];
                int ny=z.y+dir[i][1];
                if(nx<0||nx>=n||ny<0||ny>=n) continue;
                if(vis[nx][ny]) continue;
                if(a[nx][ny]==0) q0.push(node(nx,ny,z.dis));
                else q1.push(node(nx,ny,z.dis+1));
                vis[nx][ny]=1;
            }
        }
        if(!judge)
        {
            int sz=(int)ve.size();
            for(int i=0;i<sz;i++)
            {
                q1.push(ve[i]);
                vis[ve[i].x][ve[i].y]=1;
            }
            ve.clear();
        }
        while(!q1.empty())
        {
            node z=q1.front();q1.pop();
            if(z.x==n-1&&z.y==n-1) return z.dis;
            for(int i=0;i<4;i++)
            {
                int nx=z.x+dir[i][0];
                int ny=z.y+dir[i][1];
                if(nx<0||nx>=n||ny<0||ny>=n) continue;
                if(vis[nx][ny]) continue;
                if(a[nx][ny]==0)
                {
                    q0.push(node(nx,ny,z.dis));
                    vis[nx][ny]=1;
                }
                else ve.push_back(node(nx,ny,z.dis+1));
            }
        }
    }
}
int main()
{

    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&a[i][j]);
        memset(vis,0,sizeof(vis));
        printf("%d\n",bfs());
    }
    return 0;
}

第三题