Advertisement
Josif_tepe

Untitled

Apr 29th, 2022
883
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.11 KB | None
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. int main() {
  6.     int redovi, koloni;
  7.     cin >> redovi >> koloni;
  8.    
  9.     char lavirint[redovi][koloni];
  10.     int poseteno[redovi][koloni];
  11.     int pocetok_i, pocetok_j;
  12.     for(int i = 0; i < redovi; i++) {
  13.         for(int j = 0; j < koloni; j++) {
  14.             cin >> lavirint[i][j];
  15.            
  16.             if(lavirint[i][j] == 'P') {
  17.                 pocetok_i = i;
  18.                 pocetok_j = j;
  19.             }
  20.         }
  21.     }
  22.     for(int i = 0; i < redovi; i++) {
  23.         for(int j = 0; j < koloni; j++) {
  24.             poseteno[i][j] = 0;
  25.         }
  26.     }
  27.     queue<int> Q;
  28.     Q.push(pocetok_i); // na koj red se naogame
  29.     Q.push(pocetok_j); // na koja kolona se naogame
  30.     Q.push(0); // kolku polinja sme pominale od pocetnoto pole P do poleto K
  31.    
  32.     poseteno[pocetok_i][pocetok_j] = 1;
  33.     while(Q.size() > 0) {
  34.         int ci = Q.front();
  35.         Q.pop();
  36.         int cj = Q.front();
  37.         Q.pop();
  38.         int polinja = Q.front();
  39.         Q.pop();
  40.         if(lavirint[ci][cj] == 'K') {
  41.             cout << polinja << endl;
  42.            
  43.         }
  44.         if(ci + 1 < redovi and lavirint[ci + 1][cj] != '#' and poseteno[ci + 1][cj] == 0) {
  45.             Q.push(ci + 1);
  46.             Q.push(cj);
  47.             Q.push(polinja + 1);
  48.             poseteno[ci + 1][cj] = 1;
  49.         }
  50.         if(ci - 1 >= 0 and lavirint[ci - 1][cj] != '#' and poseteno[ci - 1][cj] == 0) {
  51.             Q.push(ci - 1);
  52.             Q.push(cj);
  53.             Q.push(polinja + 1);
  54.             poseteno[ci - 1][cj] = 1;
  55.         }
  56.         if(cj + 1 < koloni and lavirint[ci][cj + 1] != '#' and poseteno[ci][cj + 1] == 0) {
  57.             Q.push(ci);
  58.             Q.push(cj + 1);
  59.             Q.push(polinja + 1);
  60.             poseteno[ci][cj + 1] = 1;
  61.         }
  62.         if(cj - 1 >= 0 and lavirint[ci][cj - 1] != '#' and poseteno[ci][cj - 1] == 0) {
  63.             Q.push(ci);
  64.             Q.push(cj - 1);
  65.             Q.push(polinja + 1);
  66.             poseteno[ci][cj - 1] = 1;
  67.         }
  68.     }
  69.    
  70.     return 0;
  71. }
  72. /*
  73.  
  74. 4 5
  75. .....
  76. P#...
  77. .....
  78. #.K..
  79.  **/
  80.  
Advertisement
RAW Paste Data Copied
Advertisement