Advertisement
Josif_tepe

Untitled

Mar 24th, 2021
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.48 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.     int di[] = {-1, 1, 0, 0};
  44.     int dj[] = {0,  0,-1, 1};
  45.     while(!q.empty()) {
  46.         int ci = q.front();
  47.         q.pop();
  48.         int cj = q.front();
  49.         q.pop();
  50.         int cekori = q.front();
  51.         q.pop();
  52.         if(mat[ci][cj] == 'E') { // ova znaci deka sme stignale do krajot odnosno do posakuvanata destinacija
  53.             cout << "Od S do E ni trebaat " << cekori << " broj na cekori" << endl;
  54.             break;
  55.         }
  56.         for(int i = 0; i < 4; i++) {
  57.             int ti = ci + di[i];
  58.             int tj = cj + dj[i];
  59.             if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#' and !visited[ti][tj]) {
  60.                 q.push(ti);
  61.                 q.push(tj);
  62.                 q.push(cekori + 1);
  63.                 visited[ti][tj] = true;
  64.             }
  65.         }
  66.     }
  67.    
  68.     return 0;
  69. }
  70. /*
  71.  
  72.  5 5
  73.  .....
  74.  #####
  75.  S....
  76.  E....
  77.  #####
  78.  
  79.  
  80.  5 5
  81.  #..E#
  82.  .....
  83.  ##...
  84.  S....
  85.  #####
  86.  
  87.  Queue: (3, 0)
  88.  (3, 0) --> (3, 1)
  89.  Queue: (3, 1)
  90.  (3, 1) --> (3, 2)
  91.  
  92.  Queue: (3, 2) --> (3, 3); (2, 2)
  93.  
  94.  Queue(3, 3); (2, 2)
  95.  (3, 3) --> (3, 4); (2, 3)
  96.  
  97.  Queue: (2, 2), (3, 4), (2, 3)
  98.  (2, 2) --> (1, 2)
  99.  
  100.  Queue: (3, 4), (2, 3), (1, 2)
  101.  (3, 4) --> (2, 4)
  102.  
  103.  Queue: (2, 3), (1, 2), (2, 4)
  104.  (2, 3) --> (1, 3)
  105.  
  106.  Queue: (1, 2), (2, 4), (1, 3)
  107.  (1, 2) --> (1, 1);  (0, 2)
  108.  
  109.  Queue: (2, 4); (1, 3); (1, 1); (0, 2)
  110.  
  111.  (2, 4) --> (1, 4)
  112.  Queue: (1, 3); (1, 1); (0, 2); (1, 4)
  113.  
  114.  (1, 3) --> (0, 3)
  115.  */
  116.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement