Advertisement
cosenza987

saads

Jul 24th, 2023
913
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.64 KB | None | 0 0
  1. //Слава Україні, Героям слава
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 200;
  8.  
  9. bool dp[N][N];
  10.  
  11. map<pair<int, int>, string> mp = {{{1, 0}, "right"}, {{-1, 0}, "left"}, {{0, 1}, "up"}, {{0, -1}, "down"}};
  12.  
  13. int dx[] = {0, 1, 0, -1};
  14. int dy[] = {1, 0, -1, 0};
  15.  
  16. vector<pair<int, int>> v = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
  17.  
  18. int main() {
  19.     ios_base::sync_with_stdio(false);
  20.     cin.tie(nullptr);
  21.     int n;
  22.     cin >> n;
  23.     int x0, y0, xt, yt;
  24.     cin >> x0 >> y0 >> xt >> yt;
  25.     x0 += 100;
  26.     y0 += 100;
  27.     xt += 100;
  28.     yt += 100;
  29.     for(int i = 0; i < n; i++) {
  30.         int a, b;
  31.         cin >> a >> b;
  32.         dp[a + 100][b + 100] = true;
  33.     }
  34.     function<void(int, int, int, int, int)> clear = [&](int x, int y, int i, int j, int val) {
  35.         if(!val) return;
  36.         if(!dp[x][y]) {
  37.             dp[x][y] = 1;
  38.             if(x == xt and y == yt) {
  39.                 dp[x][y] = 0;
  40.                 n--;
  41.             }
  42.             return;
  43.         } else {
  44.             clear(x + i, y + j, i, j, 1);
  45.         }
  46.     };
  47.     while(n) {
  48.         int cur = INT_MAX;
  49.         pair<int, int> closest;
  50.         for(int i = 0; i < 200; i++) {
  51.             for(int j = 0; j < 200; j++) {
  52.                 if(dp[i][j]) {
  53.                     if(cur > abs(i - x0) + abs(j - y0)) {
  54.                         cur = abs(i - x0) + abs(j - y0);
  55.                         closest = {i, j};
  56.                     }
  57.                 }
  58.             }
  59.         }
  60.         while(cur > 1) {
  61.             for(int i = 0; i < 4; i++) {
  62.                 int x = x0 + dx[i], y = y0 + dy[i];
  63.                 if(cur > abs(x - closest.first) + abs(y - closest.second)) {
  64.                     cur = abs(x - closest.first) + abs(y - closest.second);
  65.                     clear(x + dx[i], y + dy[i], dx[i], dy[i], dp[x][y]);
  66.                     dp[x][y] = false;
  67.                     cout << mp[{dx[i], dy[i]}] << "\n";
  68.                     x0 = x;
  69.                     y0 = y;
  70.                     break;
  71.                 }
  72.             }
  73.         }
  74.         vector<pair<int, int>> tmp = v;
  75.         if(closest.first - x0 == -1) {
  76.             rotate(tmp.begin(), tmp.begin() + 2, tmp.end());
  77.         } else if(closest.second - y0 == -1) {
  78.             rotate(tmp.begin(), tmp.begin() + 1, tmp.end());
  79.         } else if(closest.second - y0 == 1) {
  80.             rotate(tmp.begin(), tmp.begin() + 3, tmp.end());
  81.         }
  82.         for(int j = 0; j < 4; j++) {
  83.             if(j) {
  84.                 x0 -= tmp[j].first;
  85.                 y0 -= tmp[j].second;
  86.                 clear(x0 - tmp[j].first, y0 - tmp[j].second, -tmp[j].first, -tmp[j].second, dp[x0][y0]);
  87.                 cout << mp[{-tmp[j].first, -tmp[j].second}] << "\n";
  88.                 dp[x0][y0] = false;
  89.                 x0 += tmp[j - 1].first;
  90.                 y0 += tmp[j - 1].second;
  91.                 cout << mp[tmp[j - 1]] << "\n";
  92.                 clear(x0 + tmp[j - 1].first, y0 + tmp[j - 1].second, tmp[j - 1].first, tmp[j - 1].second, dp[x0][y0]);
  93.                 dp[x0][y0] = false;
  94.             }
  95.             while(abs(x0 + tmp[j].first - xt) + abs(y0 + tmp[j].second - yt) > abs(x0 + 2 * tmp[j].first - xt) + abs(y0 + 2 * tmp[j].second - yt)) {
  96.                 x0 += tmp[j].first;
  97.                 y0 += tmp[j].second;
  98.                 clear(x0 + tmp[j].first, y0 + tmp[j].second, tmp[j].first, tmp[j].second, dp[x0][y0]);
  99.                 dp[x0][y0] = false;
  100.                 cout << mp[tmp[j]] << "\n";
  101.                 if(x0 == xt and y0 == yt) break;
  102.             }
  103.             if(abs(x0 + tmp[j].first - xt) + abs(y0 + tmp[j].second - yt) == 0) break;
  104.         }
  105.     }
  106.     return 0;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement