fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 2e3 + 5;
  5. const long long MaxVal = 1e2 + 5;
  6.  
  7. long long n;
  8. long long a[MaxN][MaxN];
  9.  
  10. long long dx[4]={-1,0,1,0};
  11. long long dy[4]={0,1,0,-1};
  12.  
  13. long long visited[MaxN][MaxN];
  14. long long dis[MaxN][MaxN];
  15.  
  16. vector<pair<long long,long long>> pos[MaxVal];
  17.  
  18. bool used[MaxVal];
  19.  
  20. void bfs(long long i,long long j)
  21. {
  22.     queue<pair<long long,long long>> qu;
  23.  
  24.     qu.push({i,j});
  25.  
  26.     visited[i][j]=true;
  27.     dis[i][j]=0;
  28.  
  29.     while(!qu.empty())
  30.     {
  31.         long long x=qu.front().first;
  32.         long long y=qu.front().second;
  33.  
  34.         qu.pop();
  35.  
  36.         if(!used[a[x][y]])
  37.         {
  38.             used[a[x][y]]=true;
  39.  
  40.             for(auto p:pos[a[x][y]])
  41.             {
  42.                 long long new_x=p.first;
  43.                 long long new_y=p.second;
  44.  
  45.                 if(!visited[new_x][new_y])
  46.                 {
  47.                     visited[new_x][new_y]=true;
  48.  
  49.                     dis[new_x][new_y]=dis[x][y]+1;
  50.  
  51.                     qu.push({new_x,new_y});
  52.                 }
  53.             }
  54.         }
  55.  
  56.  
  57.         for(long long t=0;t<4;t++)
  58.         {
  59.             long long new_x=x+dx[t];
  60.             long long new_y=y+dy[t];
  61.  
  62.             if(new_x<1||new_x>n||new_y<1||new_y>n)
  63.             {
  64.                 continue;
  65.             }
  66.  
  67.             if(!visited[new_x][new_y])
  68.             {
  69.                 visited[new_x][new_y]=true;
  70.  
  71.                 dis[new_x][new_y]=dis[x][y]+1;
  72.  
  73.                 qu.push({new_x,new_y});
  74.             }
  75.         }
  76.     }
  77. }
  78.  
  79. void input()
  80. {
  81.     cin>>n;
  82.  
  83.     for(long long i=1;i<=n;i++)
  84.     {
  85.         for(long long j=1;j<=n;j++)
  86.         {
  87.             cin>>a[i][j];
  88.  
  89.             pos[a[i][j]].push_back({i,j});
  90.  
  91.             visited[i][j]=false;
  92.         }
  93.     }
  94. }
  95.  
  96. void solve()
  97. {
  98.     bfs(1,1);
  99.  
  100.     cout<<dis[n][n];
  101. }
  102.  
  103. int main()
  104. {
  105.     ios_base::sync_with_stdio(0);
  106.     cin.tie(0);
  107.  
  108.     input();
  109.     solve();
  110.  
  111.     return 0;
  112. }
Success #stdin #stdout 0s 5580KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FyRG1s
language:
C++14 (gcc 8.3)
created:
19 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!