Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Слава Україні, Героям слава
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 200;
- bool dp[N][N];
- map<pair<int, int>, string> mp = {{{1, 0}, "right"}, {{-1, 0}, "left"}, {{0, 1}, "up"}, {{0, -1}, "down"}};
- int dx[] = {0, 1, 0, -1};
- int dy[] = {1, 0, -1, 0};
- vector<pair<int, int>> v = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int n;
- cin >> n;
- int x0, y0, xt, yt;
- cin >> x0 >> y0 >> xt >> yt;
- x0 += 100;
- y0 += 100;
- xt += 100;
- yt += 100;
- for(int i = 0; i < n; i++) {
- int a, b;
- cin >> a >> b;
- dp[a + 100][b + 100] = true;
- }
- function<void(int, int, int, int, int)> clear = [&](int x, int y, int i, int j, int val) {
- if(!val) return;
- if(!dp[x][y]) {
- dp[x][y] = 1;
- if(x == xt and y == yt) {
- dp[x][y] = 0;
- n--;
- }
- return;
- } else {
- clear(x + i, y + j, i, j, 1);
- }
- };
- while(n) {
- int cur = INT_MAX;
- pair<int, int> closest;
- for(int i = 0; i < 200; i++) {
- for(int j = 0; j < 200; j++) {
- if(dp[i][j]) {
- if(cur > abs(i - x0) + abs(j - y0)) {
- cur = abs(i - x0) + abs(j - y0);
- closest = {i, j};
- }
- }
- }
- }
- while(cur > 1) {
- for(int i = 0; i < 4; i++) {
- int x = x0 + dx[i], y = y0 + dy[i];
- if(cur > abs(x - closest.first) + abs(y - closest.second)) {
- cur = abs(x - closest.first) + abs(y - closest.second);
- clear(x + dx[i], y + dy[i], dx[i], dy[i], dp[x][y]);
- dp[x][y] = false;
- cout << mp[{dx[i], dy[i]}] << "\n";
- x0 = x;
- y0 = y;
- break;
- }
- }
- }
- vector<pair<int, int>> tmp = v;
- if(closest.first - x0 == -1) {
- rotate(tmp.begin(), tmp.begin() + 2, tmp.end());
- } else if(closest.second - y0 == -1) {
- rotate(tmp.begin(), tmp.begin() + 1, tmp.end());
- } else if(closest.second - y0 == 1) {
- rotate(tmp.begin(), tmp.begin() + 3, tmp.end());
- }
- for(int j = 0; j < 4; j++) {
- if(j) {
- x0 -= tmp[j].first;
- y0 -= tmp[j].second;
- clear(x0 - tmp[j].first, y0 - tmp[j].second, -tmp[j].first, -tmp[j].second, dp[x0][y0]);
- cout << mp[{-tmp[j].first, -tmp[j].second}] << "\n";
- dp[x0][y0] = false;
- x0 += tmp[j - 1].first;
- y0 += tmp[j - 1].second;
- cout << mp[tmp[j - 1]] << "\n";
- clear(x0 + tmp[j - 1].first, y0 + tmp[j - 1].second, tmp[j - 1].first, tmp[j - 1].second, dp[x0][y0]);
- dp[x0][y0] = false;
- }
- 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)) {
- x0 += tmp[j].first;
- y0 += tmp[j].second;
- clear(x0 + tmp[j].first, y0 + tmp[j].second, tmp[j].first, tmp[j].second, dp[x0][y0]);
- dp[x0][y0] = false;
- cout << mp[tmp[j]] << "\n";
- if(x0 == xt and y0 == yt) break;
- }
- if(abs(x0 + tmp[j].first - xt) + abs(y0 + tmp[j].second - yt) == 0) break;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement