#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; } 第三题