SHARE
TWEET

Untitled

a guest Jan 25th, 2020 142 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define sc second
  4. #define fr first
  5. #define ll long long
  6. #define pii pair <int, int>
  7.  
  8. using namespace std;
  9.  
  10. int main() {
  11.     ios_base::sync_with_stdio(0);
  12.     cin.tie(0); cout.tie(0);
  13.     int n, m, x, y;
  14.     cin >> n >> m >> x >> y;
  15.     x--; y--;
  16.     vector <int> chn(6);
  17.     vector <vector <pii>> go(6);
  18.     go[0] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
  19.     go[1] = {{-2, -1}, {-2, 1}, {2, 1}, {2, -1},
  20.              {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
  21.     go[2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
  22.     go[3] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
  23.     go[4] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1},
  24.              {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
  25.     go[5] = go[4];
  26.     for (int i = 0; i < 6; i++) cin >> chn[i];
  27.     vector <vector <bool>> free(n, vector <bool> (m));
  28.     for (int i = 0; i < n; i++) {
  29.         for (int j = 0; j < m; j++) {
  30.             char c;
  31.             cin >> c;
  32.             if (c == '#') free[i][j] = 1;
  33.         }
  34.     }
  35.     ll inf = 1e18;
  36.     vector<vector <ll>> d(n, vector <ll> (m, inf));
  37.     vector<vector <int>> prev(n, vector <int> (m));
  38.     set <pair <ll, pii>> q;
  39.     d[x][y] = 0;
  40.     q.insert({d[x][y], {x, y}});
  41.     while (!q.empty()) {
  42.         pii v = q.begin()->sc;
  43.         q.erase(q.begin());
  44.         for (int i = 0; i < 6; i++) {
  45.             for (auto j : go[i]) {
  46.                 int go_x = v.fr + j.fr, go_y = v.sc + j.sc;
  47.                 if (go_x >= 0 && go_x < n && go_y >= 0 && go_y < m && !free[go_x][go_y]) {
  48.                     if (i >= 2 && i < 5) {
  49.                         go_x -= j.fr, go_y -= j.sc;
  50.                         for (int k = 0; k < 8; k++) {
  51.                             go_x += j.fr, go_y += j.sc;
  52.                             if (go_x < 0 || go_x >= n || go_y < 0 || go_y >= m || free[go_x][go_y]) break;
  53.                             if (d[v.fr][v.sc] + 1 + (prev[v.fr][v.sc] == i ? 0 : chn[i]) < d[go_x][go_y]) {
  54.                                 q.erase({d[go_x][go_y], {go_x, go_y}});
  55.                                 d[go_x][go_y] = d[v.fr][v.sc] + 1 + (prev[v.fr][v.sc] == i ? 0 : chn[i]);
  56.                                 prev[go_x][go_y] = i;
  57.                                 q.insert({d[go_x][go_y], {go_x, go_y}});
  58.                             }
  59.                         }
  60.                     } else if (d[v.fr][v.sc] + 1 + (prev[v.fr][v.sc] == i ? 0 : chn[i]) < d[go_x][go_y]) {
  61.                         q.erase({d[go_x][go_y], {go_x, go_y}});
  62.                         d[go_x][go_y] = d[v.fr][v.sc] + 1 + (prev[v.fr][v.sc] == i ? 0 : chn[i]);
  63.                         prev[go_x][go_y] = i;
  64.                         q.insert({d[go_x][go_y], {go_x, go_y}});
  65.                     }
  66.                 }
  67.             }
  68.         }
  69.     }
  70.     pii ans = {x, y};
  71.     for (int i = 0; i < n; i++) {
  72.         for (int j = 0; j < m; j++) {
  73.             if (d[i][j] > d[ans.fr][ans.sc] && !free[i][j]) ans = {i, j};
  74.         }
  75.     }
  76.     cout << ans.fr + 1 << " " << ans.sc + 1 << " ";
  77.     if (d[ans.fr][ans.sc] == inf) cout << "INF";
  78.     else cout << d[ans.fr][ans.sc];
  79.     return 0;
  80. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top