Advertisement
Josif_tepe

Untitled

Feb 28th, 2021
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.64 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.     int di[] = {-1, 1, 0, 0};
  29.     int dj[] = {0,  0, -1,1};
  30.     queue<int> q;
  31.     q.push(si);
  32.     q.push(sj);
  33.     q.push(0);
  34.     visited[si][sj] = true;
  35.     while(!q.empty()) {
  36.         int ci = q.front(); // momentalno i od poleto
  37.         q.pop();
  38.         int cj = q.front(); // momentalno j od poleto
  39.         q.pop();
  40.         int dist = q.front();
  41.         q.pop();
  42.         cout << ci + 1 << " " << cj + 1 << " " << dist << endl;
  43.         if(mat[ci][cj] == 'E') {
  44.             cout << dist << endl;
  45.             break;
  46.         }
  47.         for(int i = 0; i < 4; i++) {
  48.             int ti = ci + di[i];
  49.             int tj = cj + dj[i];
  50.             if(ti < 0 or tj < 0 or ti >= n or tj >= m) continue;
  51.             if(visited[ti][tj]) continue;
  52.             if(mat[ti][tj] == '#') continue;
  53.             visited[ti][tj] = true;
  54.             q.push(ti);
  55.             q.push(tj);
  56.             q.push(dist + 1);
  57.         }
  58.        
  59.     }
  60.     return 0;
  61. }
  62. /*
  63. #####
  64. ..S..
  65. ..#..
  66.  E....
  67. #####
  68.  visited[n][m]
  69.  Queue: (1, 2, 0)
  70.  visited[1][2] = true;
  71.  
  72.  (1, 2) --> (1, 3); (1, 1)
  73.  
  74.  Queue: (1, 3, 1), (1, 1, 1)
  75.  visited[1][3] = true
  76.  visited[1][1] = true
  77.  
  78.  (1, 3) --> (1, 4); (2, 3)
  79.  
  80.  Queue: (1, 1, 1); (1, 4, 2); (2, 3, 2)
  81.  visited[1][4] = true;
  82.  visited[2][3] = true;
  83.  
  84.  (1, 1) --> (1, 0); (2, 1)
  85.  
  86.  Queue: (1, 4, 2); (2, 3, 2); (1, 0, 2); (2, 1, 2)
  87.  visited[1][0] = true;
  88.  visited[2][1] = true;
  89.  
  90.  (1, 4) --> (2, 4, 3)
  91.  
  92.  Queue: (2, 3, 2); (1, 0, 2); (2, 1, 2); (2, 4, 3)
  93.  visited[2][4] = true;
  94.  
  95.  (2, 3) --> (3, 3, 3)
  96.  
  97.  Queue: (1, 0, 2); (2, 1, 2); (2, 4, 3): (3, 3, 3)
  98.  visited[3][3] = true;
  99.  
  100.  QueueL (2, 1, 2); (2, 4, 3); (3, 3, 3)
  101.  (2, 1) --> (2, 0, 3); (3, 1, 3)
  102.  
  103.  Queue: (2, 4, 3); (3, 3, 3); (2, 0, 3); (3, 1, 3)
  104.  visited[2][0] = true;
  105.  visited[3][1]
  106.  
  107.  (2, 4) --> (3, 4)
  108.  Queue: (3, 3, 3); (2, 0, 3); (3, 1, 3); (3, 4, 4)
  109.  visited[3][4] = true;
  110.  
  111.  (3, 3) --> (3, 2)
  112.  
  113.  QueueL (2, 0, 3); (3, 1, 3); (3, 4, 4); (3, 2, 4)
  114.  visited[3][2] = true;
  115.  (2, 0, 3) --> (3, 0, 4); ANSWER
  116.  
  117.  **/
  118.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement