Advertisement
Josif_tepe

Untitled

Jun 3rd, 2022
852
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. #include <cstring>
  4. using namespace std;
  5.  
  6. int main() {
  7.     int redovi, koloni;
  8.     cin >> redovi >> koloni;
  9.    
  10.     char lavirint[redovi][koloni];
  11.     int poseteno[redovi][koloni];
  12.    
  13.     int si, sj; // kaj se naoga kukjata na sashe
  14.     int ei, ej; // kaj se naoga kukjata na elena
  15.     for(int i = 0; i < redovi; i++) {
  16.         for(int j = 0; j < koloni; j++) {
  17.             cin >> lavirint[i][j];
  18.            
  19.             if(lavirint[i][j] == 'S') {
  20.                 si = i;
  21.                 sj = j;
  22.             }
  23.             if(lavirint[i][j] == 'E') {
  24.                 ei = i;
  25.                 ej = j;
  26.             }
  27.         }
  28.     }
  29.    
  30.     int di[] = {+1, -1, 0, 0};
  31.     int dj[] = {0 , 0,  -1, +1};
  32.     int najgolem_pat = -1;
  33.     for(int i = 0; i < redovi; i++) {
  34.         for(int j = 0; j < koloni; j++) {
  35.             if(lavirint[i][j] == '#') {
  36.                 int patot_do_sashe = -1; // da receme deka na pocetok ne znaeme dali ke stigneme do kukjata na sashe i do kukjata na elena, zatoa gi stavame vrednostite ednakvi na -1
  37.                 int patot_do_elena = -1;
  38.                 memset(poseteno, 0, sizeof poseteno);
  39.                
  40.                 queue<int> Q;
  41.                 Q.push(i);
  42.                 Q.push(j);
  43.                 Q.push(0);
  44.                
  45.                 poseteno[i][j] = 1;
  46.                
  47.                 // pocnuvame so BFS
  48.                 while(Q.size() > 0) {
  49.                     int ci = Q.front();
  50.                     Q.pop();
  51.                     int cj = Q.front();
  52.                     Q.pop();
  53.                     int cekor = Q.front();
  54.                     Q.pop();
  55.                    
  56.                     if(lavirint[ci][cj] == 'S') { // ko da sme trgnale od kukjata na sashe popravajki ja ovaa barichka, barichkata na poleto (i, j)
  57.                         patot_do_sashe = cekor;
  58.                     }
  59.                     if(lavirint[ci][cj] == 'E') { // ko da sme stignale do kukjata na elena popravajki ja barickata na poleto (i, j)
  60.                         patot_do_elena = cekor;
  61.                     }
  62.                     for(int k = 0; k < 4; k++) {
  63.                         int ti = ci + di[k];
  64.                         int tj = cj + dj[k];
  65.                         if(ti >= 0 and ti < redovi and tj >= 0 and tj < koloni and lavirint[ti][tj] != '#' and poseteno[ti][tj] == 0) {
  66.                             Q.push(ti);
  67.                             Q.push(tj);
  68.                             Q.push(cekor + 1);
  69.                             poseteno[ti][tj] = 1;
  70.                         }
  71.                     }
  72.                    
  73.                 }
  74.                 if(patot_do_elena != -1 and patot_do_sashe != -1) {
  75.                     if(najgolem_pat < patot_do_elena + patot_do_sashe) {
  76.                         najgolem_pat = patot_do_elena + patot_do_sashe;
  77.                     }
  78.                 }
  79.                
  80.                
  81.             }
  82.         }
  83.     }
  84.     cout << najgolem_pat << endl;
  85.     return 0;
  86. }
  87. /*
  88.  
  89.  S..#E
  90.  ###..
  91.  #....
  92.  .....
  93.  
  94.  **/
  95.  
Advertisement
RAW Paste Data Copied
Advertisement