Advertisement
Josif_tepe

Untitled

Mar 4th, 2021
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.47 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     int n, m, pi, pj, ki, kj;
  9.     cin >> n >> m;
  10.     char mat[n][m];
  11.     for(int i = 0; i< n; i++){
  12.         for(int j = 0; j < m; j++){
  13.             cin >> mat[i][j];
  14.             if (mat[i][j] == 'P'){
  15.                 pi = i;
  16.                 pj = j;
  17.             }
  18.              if (mat[i][j] == 'K'){
  19.                 ki = i;
  20.                 kj = j;
  21.             }
  22.         }
  23.     }
  24.     bool visited[3][n][m];
  25.     for(int i = 0; i < 3; i++){
  26.         for(int j = 0; j < n; j++){
  27.             for(int z = 0; z < m; z++){
  28.                 visited[i][j][z] = false;
  29.             }
  30.         }
  31.     }
  32.     visited[0][pi][pj] = true;
  33.  
  34.     int di[] = {1, -1, 0, 0, 2, -2, 0, 0, 3, -3, 0, 0};
  35.     int dj[] = {0, 0, 1, -1, 0, 0, 2, -2, 0, 0, 3, -3};
  36.  
  37.     queue<int> q;
  38.     q.push(pi);
  39.     q.push(pj);
  40.     q.push(0);
  41.     q.push(1);
  42. //    cout << pi << " " << pj << endl;
  43.  
  44.     while (!q.empty()){
  45.         int ci = q.front();
  46.         q.pop();
  47.         int cj = q.front();
  48.         q.pop();
  49.         int dist = q.front();
  50.         q.pop();
  51.         int cekor = q.front();
  52.         q.pop();
  53. //        cout << ci << " " << cj << endl;
  54. //        cout << mat[ci][cj] << " " << endl;
  55.         if(mat[ci][cj] == 'K'){
  56.             cout << dist << endl;
  57.             return 0;
  58.         }
  59.  
  60.         if (cekor == 1){
  61.             for (int i = 0; i < 4; i++){
  62.                 int ti = ci + di[i];
  63.                 int tj = cj + dj[i];
  64.                 if (ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#' and !visited[0][ti][tj]){
  65.                     visited[0][ti][tj] = true;
  66.                     q.push(ti);
  67.                     q.push(tj);
  68.                     q.push(dist + 1);
  69.                     q.push(2);
  70.                 }
  71.             }
  72.         }
  73.         else if (cekor == 2){
  74.             for (int i = 0; i < 4; i++){
  75.                 int ti = ci + di[i];
  76.                 int tj = cj + dj[i];
  77.                 if (ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#'){
  78.                     ti = ci + di[i + 4];
  79.                     tj = cj + dj[i + 4];
  80.                     if (ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#' and !visited[1][ti][tj]){
  81.                         visited[1][ti][tj] = true;
  82.                         q.push(ti);
  83.                         q.push(tj);
  84.                         q.push(dist+1);
  85.                         q.push(3);
  86.                     }
  87.                 }
  88.             }
  89.         }else if (cekor == 3){
  90.             for (int i = 0; i < 4; i++){
  91.                 int ti = ci + di[i];
  92.                 int tj = cj + dj[i];
  93.                 if (ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#'){
  94.                     ti = ci + di[i + 4];
  95.                     tj = cj + dj[i + 4];
  96.                     if (ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#'){
  97.                         ti = ci + di[i + 8];
  98.                         tj = cj + dj[i + 8];
  99.                         if (ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#' and !visited[2][ti][tj]){
  100.                             visited[2][ti][tj] = true;
  101.                             q.push(ti);
  102.                             q.push(tj);
  103.                             q.push(dist+1);
  104.                             q.push(1);
  105.                         }
  106.                     }
  107.                 }
  108.             }
  109.         }
  110.  
  111.     }
  112.  
  113.     return 0;
  114. }
  115.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement