Advertisement
cosenza987

Untitled

Sep 9th, 2021
1,148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 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.     if(x + 1 < n and l[index][x + 1][y] > dep + 1 and v[x + 1][y] == '.') {
  13.         bfs(index, x + 1, y, dep + 1);
  14.     }
  15.     if(x - 1 >= 0 and l[index][x - 1][y] > dep + 1 and v[x - 1][y] == '.') {
  16.         bfs(index, x - 1, y, dep + 1);
  17.     }
  18.     if(y + 1 < m and l[index][x][y + 1] > dep + 1 and v[x][y + 1] == '.') {
  19.         bfs(index, x, y + 1, dep + 1);
  20.     }
  21.     if(y - 1 >= 0 and l[index][x][y - 1] > dep + 1 and v[x][y - 1] == '.') {
  22.         bfs(index, x, y - 1, dep + 1);
  23.     }
  24.     return;
  25. }
  26.  
  27. int main() {
  28.     ios_base::sync_with_stdio(false);
  29.     cin.tie(0);
  30.     cin >> n >> m;
  31.     v = vector<string>(n);
  32.     for(int i = 0; i < n; i++) {
  33.         cin >> v[i];
  34.     }
  35.     l = vector<vector<vector<int>>>(4, vector<vector<int>>(n, vector<int>(m, INT_MAX)));
  36.     pair<int, int> a1, a2, b1, b2;
  37.     cin >> a1.first >> a1.second;
  38.     cin >> a2.first >> a2.second;
  39.     cin >> b1.first >> b1.second;
  40.     cin >> b2.first >> b2.second;
  41.     bfs(0, a1.first, a1.second);
  42.     bfs(1, a2.first, a2.second);
  43.     bfs(2, b1.first, b1.second);
  44.     bfs(3, b2.first, b2.second);
  45.     int ans = INT_MAX;
  46.     for(int i = 0; i < n; i++) {
  47.         for(int j = 0; j < m; j++) {
  48.             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) {
  49.                 continue;
  50.             }
  51.             //cout << i << " " << j << "\n";
  52.             ans = min(ans, l[0][i][j] + l[1][i][j] + l[2][i][j] + l[3][i][j]);
  53.         }
  54.     }
  55.     if(ans == INT_MAX) {
  56.         cout << "IMPOSSIBLE\n";
  57.     } else {
  58.         cout << ans << "\n";
  59.     }
  60.     return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement