document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #include <cstdio>
  2. #include <queue>
  3. using namespace std;
  4. const int SIZE = 1000;
  5. int a[SIZE][SIZE],N;
  6. bool Out(int x,int y){return x<0||y<0||x>=N||y>=N;}
  7. int dx[4]={1,0,-1,0};
  8. int dy[4]={0,1,0,-1};
  9. int dp[SIZE][SIZE][2];
  10. int main(){
  11.     scanf("%d",&N);
  12.     for(int i=0;i<N;i++)
  13.         for(int j=0;j<N;j++)scanf("%d",&a[i][j]);
  14.     queue<int>qq;
  15.     dp[0][0][0]=dp[0][0][1]=1;
  16.     qq.push(0);
  17.     qq.push(0);
  18.     qq.push(0);
  19.     qq.push(0);
  20.     qq.push(0);
  21.     qq.push(1);
  22.     while(qq.size()){
  23.         int x=qq.front();qq.pop();
  24.         int y=qq.front();qq.pop();
  25.         int v=qq.front();qq.pop();
  26.         if(x==N-1&&y==N-1)return 0*printf("%d\\n",dp[x][y][v]);
  27.         for(int i=0;i<4;i++){
  28.             int nx=x+dx[i];
  29.             int ny=y+dy[i];
  30.             if(Out(nx,ny))continue;
  31.             if(dp[nx][ny][v^1])continue;
  32.             if(v!=(a[x][y]<a[nx][ny]))continue;
  33.             dp[nx][ny][v^1]=dp[x][y][v]+1;
  34.             qq.push(nx);qq.push(ny);qq.push(v^1);
  35.         }
  36.     }
  37.     return 0*puts("-1");
  38. }
');