fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ii pair < int , int >
  5.  
  6. const int N = 1e6 + 5;
  7. int q , n , m;
  8. vector < int > dist11[N] , distnn[N] , a[N];
  9. deque < ii > dq;
  10. int dx[] = {1 , 0 , -1 , 0};
  11. int dy[] = {0 , 1 , 0 , -1};
  12.  
  13. void BFS(int i , int j , int k , vector < int > dist[N])
  14. {
  15.     for(int i = 1 ; i <= n ; i++)
  16.         for(int j = 1 ; j <= m ; j++)
  17.             dist[i][j] = 1e9;
  18.     dist[i][j] = 0;
  19.     dq.push_back(ii(i , j));
  20.  
  21.     while(!dq.empty())
  22.     {
  23.         int u = dq.front().first;
  24.         int v = dq.front().second;
  25.         dq.pop_front();
  26.         for(int s = 0 ; s < 4 ; s++)
  27.         {
  28.             int x = u + dx[s];
  29.             int y = v + dy[s];
  30.             if(x > 0 && x <= n && y > 0 && y <= m)
  31.             {
  32.                 int w = (a[u][v] != k && a[u][v] != 3);
  33.                 if(dist[x][y] > dist[u][v] + w)
  34.                 {
  35.                     dist[x][y] = dist[u][v] + w;
  36.                     if(w == 1)
  37.                         dq.push_back(ii(x , y));
  38.                     else
  39.                         dq.push_front(ii(x , y));
  40.                 }
  41.             }
  42.         }
  43.     }
  44. }
  45.  
  46. main()
  47. {
  48.     freopen("CAFE.INP","r",stdin);
  49.      freopen("CAFE.OUT","w",stdout);
  50.     ios::sync_with_stdio(0);
  51.     cin.tie(0);
  52.     cin >> q;
  53.     while(q--)
  54.     {
  55.         cin >> n >> m;
  56.         for(int i = 0 ; i <= n + 1 ; i++)
  57.         {
  58.             for(int j = 0 ; j <= m + 1 ; j++)
  59.                 dist11[i].push_back(0) , a[i].push_back(0) , distnn[i].push_back(0);
  60.         }
  61.  
  62.         for(int i = 1 ; i <= n ; i++)
  63.             for(int j = 1 ; j <= m ; j++)
  64.                 cin >> a[i][j];
  65.         BFS(1 , 1 , 2 , dist11);
  66.         BFS(n , m , 1 , distnn);
  67.  
  68.         int ans = 1e18;
  69.         for(int i = 1 ; i <= n ; i++)
  70.             for(int j = 1 ; j <= m ; j++)
  71.                 ans = min(ans , dist11[i][j] + distnn[i][j]);
  72.         cout << ans << "\n";
  73.         for(int i = 0 ; i <= n + 1 ; i++)
  74.         {
  75.             a[i].clear();
  76.             dist11[i].clear();
  77.             distnn[i].clear();
  78.         }
  79.         //exit(0);
  80.     }
  81. }
Success #stdin #stdout 0.02s 74160KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/kXaE4T
language:
C++14 (gcc 8.3)
created:
8 days 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!