Advertisement
YEZAELP

TOI10: TOI Raider

Dec 22nd, 2020 (edited)
135
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.96 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 2e9;
  5. using pi = pair <int, int>;
  6. using pii = pair < int, pi>;
  7. const int D = 2520;
  8. const int N = 110;
  9.  
  10. int di1[] = {0, 0, 1, -1, 1, -1};
  11. int dj1[] = {1, -1, 0, 0, -1, -1};
  12. int di2[] = {0, 0, 1, -1, 1, -1};
  13. int dj2[] = {1, -1, 0, 0, 1, 1};
  14.  
  15. bool visited[D][N][N];
  16. int ar[N][N];
  17. int n, m;
  18.  
  19. bool check(int i, int j){
  20.     return i >= 0 and j >=0 and i < n and j < m and ar[i][j] != 0;
  21. }
  22.  
  23. int main(){
  24.  
  25.     scanf("%d%d", &n, &m);
  26.  
  27.     for(int i=0;i<n;i++){
  28.         for(int j=0;j<m;j++){
  29.             scanf("%d", &ar[i][j]);
  30.         }
  31.     }
  32.  
  33.     queue <pii> q;
  34.     if(check((n-1)/2 - 1, 0))
  35.         q.push({1, {(n-1)/2 - 1, 0}});
  36.     if(check((n-1)/2, 0))
  37.         q.push({1, {(n-1)/2, 0}});
  38.     if(check((n-1)/2 + 1, 0))
  39.         q.push({1, {(n-1)/2 + 1, 0}});
  40.  
  41.     int ei = (n-1)/2;
  42.     int ej = m-1;
  43.     while(q.size() > 0){
  44.         int ui, uj, Dis;
  45.         Dis = q.front().first;
  46.         ui = q.front().second.first;
  47.         uj = q.front().second.second;
  48.         q.pop();
  49.  
  50.         if(ui == ei and uj == ej) {
  51.             printf("%d", Dis);
  52.             return 0;
  53.         }
  54.  
  55.         if((ui + 1) % 2 == 0){
  56.             for(int d=0;d<6;d++){
  57.                 int vi = ui + di1[d];
  58.                 int vj = uj + dj1[d];
  59.                 if(check(vi, vj) and !visited[(Dis + 1) % D][vi][vj] and (Dis + 1) % ar[vi][vj] == 0){
  60.                     visited[(Dis + 1) % D][vi][vj] = true;
  61.                     q.push({Dis + 1, {vi, vj}});
  62.                 }
  63.             }
  64.         }
  65.         else {
  66.             for(int d=0;d<6;d++){
  67.                 int vi = ui + di2[d];
  68.                 int vj = uj + dj2[d];
  69.                 if(check(vi, vj) and !visited[(Dis + 1) % D][vi][vj] and (Dis + 1) % ar[vi][vj] == 0){
  70.                     visited[(Dis + 1) % D][vi][vj] = true;
  71.                     q.push({Dis + 1, {vi, vj}});
  72.                 }
  73.             }
  74.         }
  75.     }
  76.  
  77.     return 0;
  78. }
  79.  
Advertisement
RAW Paste Data Copied
Advertisement