SHARE
TWEET

Untitled

a guest Dec 8th, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. int was[100][100];
  6. int ans = INT_MAX/2, m, n, p, q, x_fin, y_fin;
  7. vector<pair<pair<int,int>,int> > queue;
  8. vector<pair<int,int> > path;
  9. void bfs(int x, int y) {
  10.     int a, b, cur;
  11.     queue.emplace_back(make_pair(x, y), 0);
  12.     was[x][y] = true;
  13.     for (int k = 0; k < int(queue.size()); k++) {
  14.         a = queue[k].first.first;
  15.         b = queue[k].first.second;
  16.         cur = queue[k].second;
  17.         if (x_fin == a && y_fin == b)
  18.             ans = cur;
  19.         if (a+p < m && b+q < n && (!was[a+p][b+q])) {
  20.             queue.emplace_back(make_pair(a + p, b + q), cur + 1);
  21.             was[a + p][b + q] = true;
  22.         }
  23.         if (a+p < m && b-q >= 0 && (!was[a+p][b-q])) {
  24.             queue.emplace_back(make_pair(a + p, b - q), cur + 1);
  25.             was[a + p][b - q] = true;
  26.         }
  27.         if (a-p >= 0 && b+q < n && (!was[a-p][b+q])) {
  28.             queue.emplace_back(make_pair(a - p, b + q), cur + 1);
  29.             was[a - p][b + q] = true;
  30.         }
  31.         if (a-p >= 0 && b-q >= 0 && (!was[a-p][b-q])) {
  32.             queue.emplace_back(make_pair(a - p, b - q), cur + 1);
  33.             was[a - p][b - q] = true;
  34.         }
  35.         if (a+q < m && b+p < n && (!was[a+q][b+p])) {
  36.             queue.emplace_back(make_pair(a + q, b + p), cur + 1);
  37.             was[a + q][b + p] = true;
  38.         }
  39.         if (a+q < m && b-p >= 0 && (!was[a+q][b-p])) {
  40.             queue.emplace_back(make_pair(a + q, b - p), cur + 1);
  41.             was[a + q][b - p] = true;
  42.         }
  43.         if (a-q >= 0 && b+p < n && (!was[a-q][b+p])) {
  44.             queue.emplace_back(make_pair(a - q, b + p), cur + 1);
  45.             was[a - q][b + p] = true;
  46.         }
  47.         if (a-q >= 0 && b-p >= 0 && (!was[a-q][b-p])) {
  48.             queue.emplace_back(make_pair(a - q, b - p), cur + 1);
  49.             was[a - q][b - p] = true;
  50.         }
  51.     }
  52. }
  53. int main() {
  54.     int x, y, cur_x, cur_y, cur_ans, i, j;
  55.     cin >> m >> n >> p >> q >> x >> y >> x_fin >> y_fin;
  56.     x_fin--;
  57.     y_fin--;
  58.     for (i = 0; i < m; i++)
  59.         for (j = 0; j < n; j++)
  60.             was[i][j] = false;
  61.     bfs(x-1, y-1);
  62.     if (ans == INT_MAX/2)
  63.         cout << -1;
  64.     else {
  65.         cout << ans << endl;
  66.         for (i = int(queue.size()) - 1; i >= 0; i--)
  67.             if (queue[i].first.first == x_fin && queue[i].first.second == y_fin) {
  68.                 path.emplace_back(x_fin, y_fin);
  69.                 break;
  70.             }
  71.         cur_x = x_fin;
  72.         cur_y = y_fin;
  73.         cur_ans = ans;
  74.         for (j = i; j >= 0; j--) {
  75.             if (abs(queue[j].first.first - cur_x) == p && abs(queue[j].first.second - cur_y) == q &&
  76.                 queue[j].second == cur_ans - 1) {
  77.                 path.emplace_back(queue[j].first.first, queue[j].first.second);
  78.                 cur_x = queue[j].first.first;
  79.                 cur_y = queue[j].first.second;
  80.                 cur_ans = queue[j].second;
  81.             } else if (abs(queue[j].first.first - cur_x) == q && abs(queue[j].first.second - cur_y) == p &&
  82.                        queue[j].second == cur_ans - 1) {
  83.                 path.emplace_back(queue[j].first.first, queue[j].first.second);
  84.                 cur_x = queue[j].first.first;
  85.                 cur_y = queue[j].first.second;
  86.                 cur_ans = queue[j].second;
  87.             }
  88.         }
  89.         reverse(path.begin(), path.end());
  90.         for (i = 0; i < int(path.size()); i++)
  91.             cout << path[i].first+1 << " " << path[i].second+1 << endl;
  92.     }
  93.     return 0;
  94. }
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