Advertisement
Josif_tepe

Untitled

Nov 5th, 2024
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.62 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.    
  10.     char mat[n][m];
  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);
  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 cekor = q.front();
  53.         q.pop();
  54.        
  55.         if(ci == ei and cj == ej) {
  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.                
  65.                 if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#' and !visited[ti][tj]) {
  66.                     visited[ti][tj] = true;
  67.                     q.push(ti);
  68.                     q.push(tj);
  69.                     q.push(dist + 1);
  70.                     q.push(2);
  71.                 }
  72.             }
  73.         }
  74.         else if(cekor == 2) {
  75.             for(int i = 0; i < 4; i++) {
  76.                 int ti = ci + di[i];
  77.                 int tj = cj + dj[i];
  78.                
  79.                 if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#') {
  80.                     ti = ci + di2[i];
  81.                     tj = cj + dj2[i];
  82.                    
  83.                     if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#' and !visited2[ti][tj]) {
  84.                         q.push(ti);
  85.                         q.push(tj);
  86.                         q.push(dist + 1);
  87.                         q.push(3);
  88.                         visited2[ti][tj] = true;
  89.                        
  90.                     }
  91.                    
  92.                 }
  93.             }
  94.         }
  95.         else if(cekor == 3) {
  96.             for(int i = 0; i < 4; i++) {
  97.                 int ti = ci + di[i];
  98.                 int tj = cj + dj[i];
  99.                
  100.                 if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#') {
  101.                     ti = ci + di2[i];
  102.                     tj = cj + dj2[i];
  103.                    
  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.                        
  108.                         if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#' and !visited3[ti][tj]) {
  109.                             q.push(ti);
  110.                             q.push(tj);
  111.                             q.push(dist + 1);
  112.                             q.push(1);
  113.                             visited3[ti][tj] = true;
  114.                         }
  115.                        
  116.                     }
  117.                 }
  118.             }
  119.         }
  120.     }
  121.    
  122.    
  123.    
  124.     return 0;
  125. }
  126.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement