Advertisement
Josif_tepe

Untitled

May 6th, 2022
767
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.67 KB | None
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     int redovi, koloni;
  8.     cin >> redovi >> koloni;
  9.    
  10.     char lavirint[redovi][koloni];
  11.     int poseteno[redovi][koloni];
  12.     int si, sj;
  13.     int ai, aj;
  14.     int bi, bj;
  15.     int pi, pj;
  16.     for(int i = 0; i < redovi; i++) {
  17.         for(int j = 0; j < koloni; j++) {
  18.             cin >> lavirint[i][j];
  19.            
  20.             if(lavirint[i][j] == 'S') {
  21.                 si = i;
  22.                 sj = j;
  23.             }
  24.             if(lavirint[i][j] == 'A') {
  25.                 ai = i;
  26.                 aj = j;
  27.             }
  28.             if(lavirint[i][j] == 'B') {
  29.                 bi = i;
  30.                 bj = j;
  31.             }
  32.             if(lavirint[i][j] == 'P') {
  33.                 pi = i;
  34.                 pj = j;
  35.             }
  36.             poseteno[i][j] = 0;
  37.         }
  38.     }
  39.     queue<int> Q;
  40.     Q.push(si);
  41.     Q.push(sj);
  42.     Q.push(0);
  43.     int pat1 = 0;
  44.     while(Q.size() > 0) {
  45.         int ci = Q.front();
  46.         Q.pop();
  47.         int cj = Q.front();
  48.         Q.pop();
  49.         int cekori = Q.front();
  50.         Q.pop();
  51.         if(lavirint[ci][cj] == 'A') {
  52.             pat1 += cekori;
  53.             break;
  54.         }
  55.         if(ci + 1 < redovi and lavirint[ci + 1][cj] != '#' and poseteno[ci + 1][cj] == 0) {
  56.             Q.push(ci + 1);
  57.             Q.push(cj);
  58.             Q.push(cekori + 1);
  59.             poseteno[ci + 1][cj] = 1;
  60.         }
  61.         if(ci - 1 >= 0 and lavirint[ci - 1][cj] != '#' and poseteno[ci - 1][cj] == 0) {
  62.             Q.push(ci - 1);
  63.             Q.push(cj);
  64.             Q.push(cekori + 1);
  65.             poseteno[ci - 1][cj] = 1;
  66.         }
  67.         if(cj + 1 < koloni and lavirint[ci][cj + 1] != '#' and poseteno[ci][cj + 1] == 0) {
  68.             Q.push(ci);
  69.             Q.push(cj + 1);
  70.             Q.push(cekori + 1);
  71.             poseteno[ci][cj + 1] = 1;
  72.         }
  73.         if(cj - 1 >= 0 and lavirint[ci][cj - 1] != '#' and poseteno[ci][cj - 1] == 0) {
  74.             Q.push(ci);
  75.             Q.push(cj - 1);
  76.             Q.push(cekori + 1);
  77.             poseteno[ci][cj - 1] = 1;
  78.         }
  79.     }
  80.     for(int i = 0; i < redovi; i++) {
  81.         for(int j = 0; j < koloni; j++) {
  82.             poseteno[i][j] = 0;
  83.         }
  84.     }
  85.     queue<int> Q1;
  86.     Q1.push(ai);
  87.     Q1.push(aj);
  88.     Q1.push(0);
  89.     poseteno[ai][aj] = 1;
  90.    
  91.     while(Q1.size() > 0) {
  92.         int ci = Q1.front();
  93.         Q1.pop();
  94.         int cj = Q1.front();
  95.         Q1.pop();
  96.         int cekori = Q1.front();
  97.         Q1.pop();
  98.        
  99.         if(lavirint[ci][cj] == 'P') {
  100.             pat1 += cekori;
  101.             break;
  102.         }
  103.         if(ci + 1 < redovi and lavirint[ci + 1][cj] != '#' and poseteno[ci + 1][cj] == 0) {
  104.             Q1.push(ci + 1);
  105.             Q1.push(cj);
  106.             Q1.push(cekori + 1);
  107.             poseteno[ci + 1][cj] = 1;
  108.         }
  109.         if(ci - 1 >= 0 and lavirint[ci - 1][cj] != '#' and poseteno[ci - 1][cj] == 0) {
  110.             Q1.push(ci - 1);
  111.             Q1.push(cj);
  112.             Q1.push(cekori + 1);
  113.             poseteno[ci - 1][cj] = 1;
  114.         }
  115.         if(cj + 1 < koloni and lavirint[ci][cj + 1] != '#' and poseteno[ci][cj + 1] == 0) {
  116.             Q1.push(ci);
  117.             Q1.push(cj + 1);
  118.             Q1.push(cekori + 1);
  119.             poseteno[ci][cj + 1] = 1;
  120.         }
  121.         if(cj - 1 >= 0 and lavirint[ci][cj - 1] != '#' and poseteno[ci][cj - 1] == 0) {
  122.             Q1.push(ci);
  123.             Q1.push(cj - 1);
  124.             Q1.push(cekori + 1);
  125.             poseteno[ci][cj - 1] = 1;
  126.         }
  127.     }
  128.    
  129.     for(int i = 0; i < redovi; i++) {
  130.         for(int j = 0; j < koloni; j++) {
  131.             poseteno[i][j] = 0;
  132.         }
  133.     }
  134.    
  135.     queue<int> Q2;
  136.     Q2.push(si);
  137.     Q2.push(sj);
  138.     Q2.push(0);
  139.     poseteno[si][sj] = 1;
  140.     int pat2 = 0;
  141.     while(Q2.size() > 0) {
  142.         int ci = Q2.front();
  143.         Q2.pop();
  144.         int cj = Q2.front();
  145.         Q2.pop();
  146.         int cekori = Q2.front();
  147.         Q2.pop();
  148.        
  149.         if(lavirint[ci][cj] == 'B') {
  150.             pat2 += cekori;
  151.             break;
  152.         }
  153.         if(ci + 1 < redovi and lavirint[ci + 1][cj] != '#' and poseteno[ci + 1][cj] == 0) {
  154.             Q2.push(ci + 1);
  155.             Q2.push(cj);
  156.             Q2.push(cekori + 1);
  157.             poseteno[ci + 1][cj] = 1;
  158.         }
  159.         if(ci - 1 >= 0 and lavirint[ci - 1][cj] != '#' and poseteno[ci - 1][cj] == 0) {
  160.             Q2.push(ci - 1);
  161.             Q2.push(cj);
  162.             Q2.push(cekori + 1);
  163.             poseteno[ci - 1][cj] = 1;
  164.         }
  165.         if(cj + 1 < koloni and lavirint[ci][cj + 1] != '#' and poseteno[ci][cj + 1] == 0) {
  166.             Q2.push(ci);
  167.             Q2.push(cj + 1);
  168.             Q2.push(cekori + 1);
  169.             poseteno[ci][cj + 1] = 1;
  170.         }
  171.         if(cj - 1 >= 0 and lavirint[ci][cj - 1] != '#' and poseteno[ci][cj - 1] == 0) {
  172.             Q2.push(ci);
  173.             Q2.push(cj - 1);
  174.             Q2.push(cekori + 1);
  175.             poseteno[ci][cj - 1] = 1;
  176.         }
  177.        
  178.     }
  179.    
  180.     for(int i = 0; i < redovi; i++) {
  181.         for(int j = 0; j < koloni; j++) {
  182.             poseteno[i][j] = 0;
  183.         }
  184.     }
  185.     queue<int> Q3;
  186.     Q3.push(bi);
  187.     Q3.push(bj);
  188.     Q3.push(0);
  189.     poseteno[bi][bj] = 1;
  190.    
  191.     while(Q3.size() > 0) {
  192.         int ci = Q3.front();
  193.         Q3.pop();
  194.         int cj = Q3.front();
  195.         Q3.pop();
  196.         int cekori = Q3.front();
  197.         Q3.pop();
  198.        
  199.         if(lavirint[ci][cj] == 'P') {
  200.             pat2 += cekori;
  201.             break;
  202.         }
  203.         if(ci + 1 < redovi and lavirint[ci + 1][cj] != '#' and poseteno[ci + 1][cj] == 0) {
  204.             Q3.push(ci + 1);
  205.             Q3.push(cj);
  206.             Q3.push(cekori + 1);
  207.             poseteno[ci + 1][cj] = 1;
  208.         }
  209.         if(ci - 1 >= 0 and lavirint[ci - 1][cj] != '#' and poseteno[ci - 1][cj] == 0) {
  210.             Q3.push(ci - 1);
  211.             Q3.push(cj);
  212.             Q3.push(cekori + 1);
  213.             poseteno[ci - 1][cj] = 1;
  214.         }
  215.         if(cj + 1 < koloni and lavirint[ci][cj + 1] != '#' and poseteno[ci][cj + 1] == 0) {
  216.             Q3.push(ci);
  217.             Q3.push(cj + 1);
  218.             Q3.push(cekori + 1);
  219.             poseteno[ci][cj + 1] = 1;
  220.         }
  221.         if(cj - 1 >= 0 and lavirint[ci][cj - 1] != '#' and poseteno[ci][cj - 1] == 0) {
  222.             Q3.push(ci);
  223.             Q3.push(cj - 1);
  224.             Q3.push(cekori + 1);
  225.             poseteno[ci][cj - 1] = 1;
  226.         }
  227.     }
  228.     if(pat1 < pat2) {
  229.         cout << pat1 << endl;
  230.     }
  231.     else {
  232.         cout << pat2 << endl;
  233.     }
  234.    
  235.     return 0;
  236. }
  237.  
  238. /*
  239.  
  240.  8 8
  241.   S...#..A
  242.   ........
  243.   ...#P...
  244.   B.......
  245.   ##......
  246.   ########
  247.   ........
  248.   ........
  249.  
  250.  
  251.  **/
  252.  
Advertisement
RAW Paste Data Copied
Advertisement