Advertisement
Josif_tepe

Untitled

Mar 24th, 2021
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. int main() {
  6.     int n, m;
  7.     cin >> n >> m;
  8.     char mat[n][m];
  9.     for(int i = 0; i < n; i++) {
  10.         for(int j = 0; j < m; j++) {
  11.             cin >> mat[i][j];
  12.         }
  13.     }
  14.     // prvo da najdeme kade se naoga S i kade se naoga E
  15.     int si = -1, sj = -1;
  16.     int ei = -1, ej = -1;
  17.    
  18.     for(int i = 0; i < n; i++) {
  19.         for(int j = 0; j < m; j++) {
  20.             if(mat[i][j] == 'S') {
  21.                 si = i;
  22.                 sj = j;
  23.             }
  24.             if(mat[i][j] == 'E') {
  25.                 ei = i;
  26.                 ej = j;
  27.             }
  28.         }
  29.     }
  30.    
  31.     bool visited[n][m]; // ke ni kazuva koi polinja sme gi posetile a koi ne
  32.     for(int i = 0; i < n; i++) {
  33.         for(int j = 0; j < m; j++) {
  34.             visited[i][j] = false;
  35.         }
  36.     }
  37.     queue<int> q;
  38.     q.push(si);
  39.     q.push(sj);
  40.     q.push(0); // kolku cekori sum napravil od poleto S do momentalnoto pole
  41.     visited[si][sj] = true;
  42.    
  43.     while(!q.empty()) {
  44.         int ci = q.front();
  45.         q.pop();
  46.         int cj = q.front();
  47.         q.pop();
  48.         int cekori = q.front();
  49.         q.pop();
  50.         if(mat[ci][cj] == 'E') { // ova znaci deka sme stignale do krajot odnosno do posakuvanata destinacija
  51.             cout << "Od S do E ni trebaat " << cekori << " broj na cekori" << endl;
  52.             break;
  53.         }
  54.         if(ci + 1 < n and mat[ci + 1][cj] != '#' and !visited[ci + 1][cj]) { // sosed dole
  55.             q.push(ci + 1);
  56.             q.push(cj);
  57.             q.push(cekori + 1);
  58.             visited[ci + 1][cj] = true; // ne sakame da se vrakame nazad
  59.         }
  60.         if(ci - 1 >= 0 and mat[ci - 1][cj] != '#' and !visited[ci - 1][cj]) { // sosed gore
  61.             q.push(ci - 1);
  62.             q.push(cj);
  63.             q.push(cekori + 1);
  64.             visited[ci - 1][cj] = true;
  65.         }
  66.         if(cj + 1  < m and mat[ci][cj + 1] != '#' and !visited[ci][cj + 1]) {
  67.             q.push(ci);
  68.             q.push(cj + 1);
  69.             q.push(cekori + 1);
  70.             visited[ci][cj + 1] = true;
  71.         }
  72.         if(cj - 1 >= 0 and mat[ci][cj - 1] != '#' and !visited[ci][cj - 1]) {
  73.             q.push(ci);
  74.             q.push(cj - 1);
  75.             q.push(cekori + 1);
  76.             visited[ci][cj - 1] = true;
  77.         }
  78.     }
  79.    
  80.     return 0;
  81. }
  82. /*
  83.  
  84.  5 5
  85.  .....
  86.  #####
  87.  S....
  88.  E....
  89.  #####
  90.  
  91.  
  92.  5 5
  93.  #..E#
  94.  .....
  95.  ##...
  96.  S....
  97.  #####
  98.  
  99.  Queue: (3, 0)
  100.  (3, 0) --> (3, 1)
  101.  Queue: (3, 1)
  102.  (3, 1) --> (3, 2)
  103.  
  104.  Queue: (3, 2) --> (3, 3); (2, 2)
  105.  
  106.  Queue(3, 3); (2, 2)
  107.  (3, 3) --> (3, 4); (2, 3)
  108.  
  109.  Queue: (2, 2), (3, 4), (2, 3)
  110.  (2, 2) --> (1, 2)
  111.  
  112.  Queue: (3, 4), (2, 3), (1, 2)
  113.  (3, 4) --> (2, 4)
  114.  
  115.  Queue: (2, 3), (1, 2), (2, 4)
  116.  (2, 3) --> (1, 3)
  117.  
  118.  Queue: (1, 2), (2, 4), (1, 3)
  119.  (1, 2) --> (1, 1);  (0, 2)
  120.  
  121.  Queue: (2, 4); (1, 3); (1, 1); (0, 2)
  122.  
  123.  (2, 4) --> (1, 4)
  124.  Queue: (1, 3); (1, 1); (0, 2); (1, 4)
  125.  
  126.  (1, 3) --> (0, 3)
  127.  */
  128.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement