Advertisement
Josif_tepe

Untitled

Feb 28th, 2021
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.08 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5. typedef long long  ll;
  6.  
  7. int main() {
  8.     ios_base::sync_with_stdio(false);
  9.     int n, m;
  10.     cin >> n >> m;
  11.     char mat[n][m];
  12.     for(int i = 0; i < n; i++) {
  13.         for(int j = 0; j < m; j++) {
  14.             cin >> mat[i][j];
  15.         }
  16.     }
  17.     bool visited[n][m];
  18.     int si = -1, sj = -1; // redot na S, kolonata na S
  19.     for(int i = 0; i < n; i++) {
  20.         for(int j = 0; j < m; j++) {
  21.             visited[i][j] = false;
  22.             if(mat[i][j] == 'S') {
  23.                 si = i;
  24.                 sj = j;
  25.             }
  26.         }
  27.     }
  28.     queue<int> q;
  29.     q.push(si);
  30.     q.push(sj);
  31.     q.push(0);
  32.     visited[si][sj] = true;
  33.     while(!q.empty()) {
  34.         int ci = q.front(); // momentalno i od poleto
  35.         q.pop();
  36.         int cj = q.front(); // momentalno j od poleto
  37.         q.pop();
  38.         int dist = q.front();
  39.         q.pop();
  40.         cout << ci + 1 << " " << cj + 1 << " " << dist << endl;
  41.         if(mat[ci][cj] == 'E') {
  42.             cout << dist << endl;
  43.             break;
  44.         }
  45.         // siri se site negovi sosedi
  46.         if(ci + 1 < n and mat[ci + 1][cj] != '#' and !visited[ci + 1][cj]) {
  47.             visited[ci + 1][cj] = true;
  48.             q.push(ci + 1);
  49.             q.push(cj);
  50.             q.push(dist + 1);
  51.         }
  52.         if(ci - 1 >= 0 and mat[ci - 1][cj] != '#' and !visited[ci - 1][cj]) {
  53.             visited[ci - 1][cj] = true;
  54.             q.push(ci - 1);
  55.             q.push(cj);
  56.             q.push(dist + 1);
  57.         }
  58.         if(cj + 1 < m and mat[ci][cj + 1] != '#' and !visited[ci][cj + 1]) {
  59.             visited[ci][cj + 1] = true;
  60.             q.push(ci);
  61.             q.push(cj + 1);
  62.             q.push(dist + 1);
  63.         }
  64.         if(cj - 1 >= 0 and mat[ci][cj - 1] != '#' and !visited[ci][cj - 1]) {
  65.             visited[ci][cj - 1] = true;
  66.             q.push(ci);
  67.             q.push(cj - 1);
  68.             q.push(dist + 1);
  69.         }
  70.        
  71.     }
  72.     return 0;
  73. }
  74. /*
  75. #####
  76. ..S..
  77. ..#..
  78.  E....
  79. #####
  80.  visited[n][m]
  81.  Queue: (1, 2, 0)
  82.  visited[1][2] = true;
  83.  
  84.  (1, 2) --> (1, 3); (1, 1)
  85.  
  86.  Queue: (1, 3, 1), (1, 1, 1)
  87.  visited[1][3] = true
  88.  visited[1][1] = true
  89.  
  90.  (1, 3) --> (1, 4); (2, 3)
  91.  
  92.  Queue: (1, 1, 1); (1, 4, 2); (2, 3, 2)
  93.  visited[1][4] = true;
  94.  visited[2][3] = true;
  95.  
  96.  (1, 1) --> (1, 0); (2, 1)
  97.  
  98.  Queue: (1, 4, 2); (2, 3, 2); (1, 0, 2); (2, 1, 2)
  99.  visited[1][0] = true;
  100.  visited[2][1] = true;
  101.  
  102.  (1, 4) --> (2, 4, 3)
  103.  
  104.  Queue: (2, 3, 2); (1, 0, 2); (2, 1, 2); (2, 4, 3)
  105.  visited[2][4] = true;
  106.  
  107.  (2, 3) --> (3, 3, 3)
  108.  
  109.  Queue: (1, 0, 2); (2, 1, 2); (2, 4, 3): (3, 3, 3)
  110.  visited[3][3] = true;
  111.  
  112.  QueueL (2, 1, 2); (2, 4, 3); (3, 3, 3)
  113.  (2, 1) --> (2, 0, 3); (3, 1, 3)
  114.  
  115.  Queue: (2, 4, 3); (3, 3, 3); (2, 0, 3); (3, 1, 3)
  116.  visited[2][0] = true;
  117.  visited[3][1]
  118.  
  119.  (2, 4) --> (3, 4)
  120.  Queue: (3, 3, 3); (2, 0, 3); (3, 1, 3); (3, 4, 4)
  121.  visited[3][4] = true;
  122.  
  123.  (3, 3) --> (3, 2)
  124.  
  125.  QueueL (2, 0, 3); (3, 1, 3); (3, 4, 4); (3, 2, 4)
  126.  visited[3][2] = true;
  127.  (2, 0, 3) --> (3, 0, 4); ANSWER
  128.  
  129.  **/
  130.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement