Advertisement
Josif_tepe

Untitled

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