Advertisement
Josif_tepe

Untitled

Aug 20th, 2024
290
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.    int n, m;
  7.    cin >> n >> m;
  8.    char mat[n][m];
  9.    bool visited[n][m];
  10.    int si, sj, ei, ej;
  11.    for(int i = 0; i < n; i++) {
  12.       for(int j = 0; j < m; j++) {
  13.          cin >> mat[i][j];
  14.  
  15.          if(mat[i][j] == 'S') {
  16.             si = i;
  17.             sj = j;
  18.          }
  19.          if(mat[i][j] == 'E') {
  20.             ei = i;
  21.             ej = j;
  22.          }
  23.          visited[i][j] = false;
  24.       }
  25.    }
  26.  
  27.    queue<int> q;
  28.    q.push(si);
  29.    q.push(sj);
  30.    q.push(0);
  31.    visited[si][sj] = true;
  32.    while(!q.empty()) {
  33.       int ci = q.front();
  34.       q.pop();
  35.       int cj = q.front();
  36.       q.pop();
  37.       int cekor = q.front();
  38.       q.pop();
  39.  
  40.       if(ci == ei and cj == ej) {
  41.          cout << cekor << endl;
  42.          break;
  43.       }
  44.  
  45.       if(ci + 1 < n and mat[ci + 1][cj] != '#' and !visited[ci + 1][cj]) {
  46.          q.push(ci + 1);
  47.          q.push(cj);
  48.          q.push(cekor + 1);
  49.          visited[ci + 1][cj] = true;
  50.       }
  51.       if(ci - 1 >= 0 and mat[ci - 1][cj] != '#' and !visited[ci - 1][cj]) {
  52.          q.push(ci - 1);
  53.          q.push(cj);
  54.          q.push(cekor + 1);
  55.          visited[ci - 1][cj] = true;
  56.       }
  57.       if(cj + 1 < m and mat[ci][cj + 1] != '#' and !visited[ci][cj + 1]) {
  58.          q.push(ci);
  59.          q.push(cj + 1);
  60.          q.push(cekor + 1);
  61.          visited[ci][cj + 1] = true;
  62.       }
  63.       if(cj - 1 >= 0 and mat[ci][cj - 1] != '#' and !visited[ci][cj - 1]) {
  64.          q.push(ci);
  65.          q.push(cj - 1);
  66.          q.push(cekor + 1);
  67.          visited[ci][cj - 1] = true;
  68.       }
  69.  
  70.  
  71.    }
  72.  
  73.  
  74.    return 0;
  75. }
  76.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement