Advertisement
cosenza987

Untitled

Sep 9th, 2021
1,080
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n, m;
  6. vector<string> v;
  7. vector<vector<vector<int>>> l;
  8.  
  9. void bfs(int index, int x, int y, int dep = 0) {
  10.     l[index][x][y] = dep;
  11.     bool vis[n][m];
  12.     memset(vis, false, sizeof(vis));
  13.     vis[x][y] = true;
  14.     queue<pair<int, pair<int, int>>> q;
  15.     q.push({0, {x, y}});
  16.     while(!q.empty()) {
  17.         auto k = q.front();
  18.         q.pop();
  19.         int d = k.first, i = k.second.first, j = k.second.second;
  20.         if(i + 1 < n and !vis[i + 1][j] and v[i + 1][j] != '#') {
  21.             vis[i + 1][j] = true;
  22.             l[index][i + 1][j] = d + 1;
  23.             q.push({d + 1, {i + 1, j}});
  24.         }
  25.         if(i - 1 >= 0 and !vis[i - 1][j] and v[i - 1][j] != '#') {
  26.             vis[i - 1][j] = true;
  27.             l[index][i - 1][j] = d + 1;
  28.             q.push({d + 1, {i - 1, j}});
  29.         }
  30.         if(j + 1 < m and !vis[i][j + 1] and v[i][j + 1] != '#') {
  31.             vis[i][j + 1] = true;
  32.             l[index][i][j + 1] = d + 1;
  33.             q.push({d + 1, {i, j + 1}});
  34.         }
  35.         if(j - 1 >= 0 and !vis[i][j - 1] and v[i][j - 1] != '#') {
  36.             vis[i][j - 1] = true;
  37.             l[index][i][j - 1] = d + 1;
  38.             q.push(make_pair(d + 1, make_pair(i, j - 1)));
  39.         }
  40.     }
  41.     return;
  42. }
  43.  
  44. int main() {
  45.     ios_base::sync_with_stdio(false);
  46.     cin.tie(0);
  47.     cin >> n >> m;
  48.     v = vector<string>(n);
  49.     for(int i = 0; i < n; i++) {
  50.         cin >> v[i];
  51.     }
  52.     l = vector<vector<vector<int>>>(4, vector<vector<int>>(n, vector<int>(m, INT_MAX)));
  53.     pair<int, int> a1, a2, b1, b2;
  54.     cin >> a1.first >> a1.second;
  55.     cin >> a2.first >> a2.second;
  56.     cin >> b1.first >> b1.second;
  57.     cin >> b2.first >> b2.second;
  58.     bfs(0, a1.first, a1.second);
  59.     bfs(1, a2.first, a2.second);
  60.     bfs(2, b1.first, b1.second);
  61.     bfs(3, b2.first, b2.second);
  62.     int ans = INT_MAX;
  63.     for(int i = 0; i < n; i++) {
  64.         for(int j = 0; j < m; j++) {
  65.             if(l[0][i][j] == INT_MAX or l[1][i][j] == INT_MAX or l[2][i][j] == INT_MAX or l[3][i][j] == INT_MAX) {
  66.                 continue;
  67.             }
  68.             //cout << i << " " << j << "\n";
  69.             ans = min(ans, l[0][i][j] + l[1][i][j] + l[2][i][j] + l[3][i][j]);
  70.         }
  71.     }
  72.     if(ans == INT_MAX) {
  73.         cout << "IMPOSSIBLE\n";
  74.     } else {
  75.         cout << ans << "\n";
  76.     }
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement