Advertisement
cosenza987

Untitled

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