SHARE
TWEET

Untitled

a guest Jan 24th, 2020 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma comment(linker, "/stack:200000000"]
  2. #pragma GCC optimize("Ofast"]
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native"]
  4. #include<iostream>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #include<map>
  9. #include<unordered_set>
  10. #include<unordered_map>
  11. #include<map>
  12. #include<algorithm>
  13. #include<queue>
  14. #include<stack>
  15. #include<cstdio>
  16. #include<random>
  17. #include<cassert>
  18. #include<sstream>
  19. #include<set>
  20.  
  21. using namespace std;
  22.  
  23. int n, m;
  24. int price[6];
  25. int inf[6] = {1, 1, 500, 500, 500, 1};
  26. vector<vector<int>> ways[6] = {
  27.     {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}, //Пешка
  28.     {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}}, //Конь
  29.     {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}, //Ладья
  30.     {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}}, //Слон
  31.     {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}, //Ферзь
  32.     {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}}; //Король
  33.  
  34. bool mp[305][305];
  35. int d[6][305][305], ans[305][305];
  36.  
  37. bool in(int i, int j){
  38.     return i >= 0 && i < n && j >= 0 && j < m;
  39. }
  40.  
  41. struct node{
  42.     int x, y, mod, dist;
  43.     node(int x = 0, int y = 0, int mod = 0, int dist = 0){
  44.         this->x = x;
  45.         this->y = y;
  46.         this->mod = mod;
  47.         this->dist = dist;
  48.     }
  49. };
  50.  
  51. struct cmp{
  52.     bool operator ()(const node & a, const node & b) const {
  53.         return a.dist < b.dist || (a.dist == b.dist && a.x < b.x) || (a.dist == b.dist && a.x == b.x && a.y < b.y) || (a.dist == b.dist && a.x == b.x && a.y == b.y && a.mod < b.mod);
  54.     }
  55. };
  56.  
  57. set<node, cmp> se;
  58.  
  59. void getWays(node & a){
  60.     int x = a.x, y = a.y, mod = a.mod, dist = a.dist;
  61.     for(auto w : ways[mod]){
  62.         for(int j = 1; j <= inf[mod]; j++){
  63.             int nx = x + w[0] * j;
  64.             int ny = y + w[1] * j;
  65.             if(!in(nx, ny) || !mp[nx][ny])break;
  66.             if(mp[nx][ny] && d[mod][nx][ny] > dist + 1){
  67.                 se.erase(node(nx, ny, mod, d[mod][nx][ny]));
  68.                 d[mod][nx][ny] = dist + 1;
  69.                 se.insert(node(nx, ny, mod, d[mod][nx][ny]));
  70.             }
  71.         }
  72.     }
  73.     for(int i = 0; i < 6; i++){
  74.         if(i == mod)continue;
  75.         if(d[i][x][y] > dist + price[i]){
  76.             se.erase(node(x, y, i, d[i][x][y]));
  77.             d[i][x][y] = dist + price[i];
  78.             se.insert(node(x, y, i, d[i][x][y]));
  79.         }
  80.     }
  81. }
  82.  
  83. void print(vector<vector<int>> & a){
  84.     for(auto i : a){
  85.         for(auto j : i)cout << j << " ";
  86.         cout << "\n";
  87.     }
  88. }
  89.  
  90. signed main(){
  91.     ios_base::sync_with_stdio(0);
  92.     cin.tie(0);
  93.     cout.tie(0);
  94.     int x, y; cin >> n >> m >> x >> y; x--; y--;
  95.     for(int i = 0; i < 6; i++)cin >> price[i];
  96.     for(int i = 0; i < n; i++){
  97.         for(int j = 0; j < m; j++){
  98.             char c; cin >> c;
  99.             if(c == '#')mp[i][j] = 0;
  100.             else mp[i][j] = 1;
  101.         }
  102.     }
  103.     for(int i = 0; i < 6; i++){
  104.         for(int j = 0; j < 305; j++){
  105.             for(int k = 0; k < 305; k++)d[i][j][k] = 1e9;
  106.         }
  107.     }
  108.     d[0][x][y] = 0;
  109.     se.insert(node(x, y, 0, 0));
  110.     while(!se.empty()){
  111.         auto v = (*se.begin()); se.erase(se.begin());
  112.         getWays(v);
  113.     }
  114.     int res = 0, resX = x, resY = y;
  115.     for(int i = 0; i < n; i++){
  116.         for(int j = 0; j < m; j++){
  117.             ans[i][j] = d[0][i][j];
  118.             for(int k = 1; k < 6; k++){
  119.                 ans[i][j] = min(ans[i][j], d[k][i][j]);
  120.             }
  121.             if(mp[i][j] && res < ans[i][j]){
  122.                 res = ans[i][j];
  123.                 resX = i;
  124.                 resY = j;
  125.             }
  126.         }
  127.     }
  128.     cout << resX + 1 << " " << resY + 1 << " ";
  129.     if(res < 1e9)cout << res << "\n";
  130.     else cout << "INF\n";
  131.     return 0;
  132. }
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