Advertisement
Josif_tepe

Untitled

Jun 3rd, 2022
940
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.48 KB | None
  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 sashe[redovi][koloni]; // ni kazuva dali mozeme da stigneme od kukjata na sashe do ova pole i vo kolku cekori
  14.     int elena[redovi][koloni];
  15.    
  16.     for(int i = 0; i < redovi; i++) {
  17.         for(int j = 0; j < koloni; j++) {
  18.             sashe[i][j] = -1;
  19.             elena[i][j] = -1;
  20.         }
  21.     }
  22.     int si, sj; // kaj se naoga kukjata na sashe
  23.     int ei, ej; // kaj se naoga kukjata na elena
  24.     for(int i = 0; i < redovi; i++) {
  25.         for(int j = 0; j < koloni; j++) {
  26.             cin >> lavirint[i][j];
  27.            
  28.             if(lavirint[i][j] == 'S') {
  29.                 si = i;
  30.                 sj = j;
  31.             }
  32.             if(lavirint[i][j] == 'E') {
  33.                 ei = i;
  34.                 ej = j;
  35.             }
  36.         }
  37.     }
  38.     int di[] = {+1, -1, 0, 0};
  39.     int dj[] = {0,  0,  - 1, +1};
  40.    
  41.     memset(poseteno, 0, sizeof poseteno);
  42.     queue<int> Q;
  43.     Q.push(si);
  44.     Q.push(sj);
  45.     Q.push(0);
  46.    
  47.     poseteno[si][sj] = 1;
  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.         if(lavirint[ci][cj] == 'E') {
  56.             cout << cekor << endl;
  57.             return 0;
  58.         }
  59.         for(int k = 0; k < 4; k++) {
  60.             int ti = ci + di[k];
  61.             int tj = cj + dj[k];
  62.             if(ti >= 0 and ti < redovi and tj >= 0 and tj < koloni and poseteno[ti][tj] == 0) {
  63.                 if(lavirint[ti][tj] == '#') {
  64.                     sashe[ti][tj] = cekor + 1;
  65.                     poseteno[ti][tj] = 1;
  66.                 }
  67.                 else {
  68.                     Q.push(ti);
  69.                     Q.push(tj);
  70.                     Q.push(cekor + 1);
  71.                     poseteno[ti][tj] = 1;
  72.                 }
  73.             }
  74.         }
  75.     }
  76.    
  77.     memset(poseteno, 0, sizeof poseteno);
  78.     queue<int> Q2;
  79.     Q2.push(ei);
  80.     Q2.push(ej);
  81.     Q2.push(0);
  82.     poseteno[ei][ej] = 1;
  83.     while(Q2.size() > 0) {
  84.         int ci = Q2.front();
  85.         Q2.pop();
  86.         int cj = Q2.front();
  87.         Q2.pop();
  88.         int cekor = Q2.front();
  89.         Q2.pop();
  90.        
  91.         for(int k = 0; k < 4; k++) {
  92.             int ti = ci + di[k];
  93.             int tj = cj + dj[k];
  94.             if(ti >= 0 and ti < redovi and tj >= 0 and tj < koloni and poseteno[ti][tj] == 0) {
  95.                 if(lavirint[ti][tj] == '#') {
  96.                     elena[ti][tj] = cekor + 1;
  97.                     poseteno[ti][tj] = 1;
  98.                 }
  99.                 else {
  100.                     Q2.push(ti);
  101.                     Q2.push(tj);
  102.                     Q2.push(cekor + 1);
  103.                     poseteno[ti][tj] = 1;
  104.                 }
  105.             }
  106.         }
  107.     }
  108.     int najgolem_pat = -1;
  109.     for(int i = 0; i < redovi; i++) {
  110.         for(int j = 0; j < koloni; j++) {
  111.             if(lavirint[i][j] == '#') {
  112.                 if(elena[i][j] != -1 and sashe[i][j] != -1) {
  113.                     if(najgolem_pat < elena[i][j] + sashe[i][j]) {
  114.                         najgolem_pat = elena[i][j] + sashe[i][j];
  115.                     }
  116.                 }
  117.             }
  118.            
  119.         }
  120.     }
  121.     cout << najgolem_pat << endl;
  122.  
  123.     return 0;
  124. }
  125. /*
  126.  
  127.  S..#E
  128.  ###..
  129.  #....
  130.  .....
  131.  
  132.  **/
  133.  
Advertisement
RAW Paste Data Copied
Advertisement