Advertisement
Josif_tepe

Untitled

May 6th, 2022
864
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.63 KB | None
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. int redovi, koloni;
  6. char lavirint[1000][1000];
  7.  
  8. int bfs(int si, int sj, int ei, int ej) {
  9.     int poseteno[redovi][koloni];
  10.     for(int i = 0; i < redovi; i++) {
  11.         for(int j = 0; j < koloni; j++) {
  12.             poseteno[i][j] = 0;
  13.         }
  14.     }
  15.     queue<int> Q;
  16.     Q.push(si);
  17.     Q.push(sj);
  18.     Q.push(0);
  19.     poseteno[si][sj] = 1;
  20.    
  21.    
  22.     while(Q.size() > 0) {
  23.         int ci = Q.front();
  24.         Q.pop();
  25.         int cj = Q.front();
  26.         Q.pop();
  27.         int cekori = Q.front();
  28.         Q.pop();
  29.        
  30.         if(ci == ei and cj == ej) {
  31.            
  32.             return cekori;
  33.         }
  34.         if(ci + 1 < redovi and lavirint[ci + 1][cj] != '#' and poseteno[ci + 1][cj] == 0) {
  35.             Q.push(ci + 1);
  36.             Q.push(cj);
  37.             Q.push(cekori + 1);
  38.             poseteno[ci + 1][cj] = 1;
  39.         }
  40.         if(ci - 1 >= 0 and lavirint[ci - 1][cj] != '#' and poseteno[ci - 1][cj] == 0) {
  41.             Q.push(ci - 1);
  42.             Q.push(cj);
  43.             Q.push(cekori + 1);
  44.             poseteno[ci - 1][cj] = 1;
  45.         }
  46.         if(cj + 1 < koloni and lavirint[ci][cj + 1] != '#' and poseteno[ci][cj + 1] == 0) {
  47.             Q.push(ci);
  48.             Q.push(cj + 1);
  49.             Q.push(cekori + 1);
  50.             poseteno[ci][cj + 1] = 1;
  51.         }
  52.         if(cj - 1 >= 0 and lavirint[ci][cj - 1] != '#' and poseteno[ci][cj - 1] == 0) {
  53.             Q.push(ci);
  54.             Q.push(cj - 1);
  55.             Q.push(cekori + 1);
  56.             poseteno[ci][cj - 1] = 1;
  57.         }
  58.     }
  59.     return 0;
  60. }
  61. int main()
  62. {
  63.     cin >> redovi >> koloni;
  64.     int si, sj;
  65.     int ai, aj;
  66.     int bi, bj;
  67.     int pi, pj;
  68.     for(int i = 0; i < redovi; i++) {
  69.         for(int j = 0; j < koloni; j++) {
  70.             cin >> lavirint[i][j];
  71.            
  72.             if(lavirint[i][j] == 'S') {
  73.                 si = i;
  74.                 sj = j;
  75.             }
  76.             if(lavirint[i][j] == 'A') {
  77.                 ai = i;
  78.                 aj = j;
  79.             }
  80.             if(lavirint[i][j] == 'B') {
  81.                 bi = i;
  82.                 bj = j;
  83.             }
  84.             if(lavirint[i][j] == 'P') {
  85.                 pi = i;
  86.                 pj = j;
  87.             }
  88.         }
  89.     }
  90.     int pat1 = bfs(si, sj, ai, aj) + bfs(ai, aj, pi, pj);
  91.     int pat2 = bfs(si, sj, bi, bj) + bfs(bi, bj, pi, pj);
  92.    
  93.     if(pat1 < pat2) {
  94.         cout << pat1 << endl;
  95.     }
  96.     else {
  97.         cout << pat2 << endl;
  98.     }
  99.        return 0;
  100. }
  101.  
  102. /*
  103.  
  104. 8 8
  105. S...#..A
  106. ........
  107. ...#P...
  108. B.......
  109. ##......
  110. ########
  111. ........
  112. ........
  113.  
  114.  
  115.  **/
  116.  
Advertisement
RAW Paste Data Copied
Advertisement