Advertisement
Josif_tepe

Untitled

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