Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int was[100][100];
- int ans = INT_MAX/2, m, n, p, q, x_fin, y_fin;
- vector<pair<pair<int,int>,int> > queue;
- vector<pair<int,int> > path;
- void bfs(int x, int y) {
- int a, b, cur;
- queue.emplace_back(make_pair(x, y), 0);
- was[x][y] = true;
- for (int k = 0; k < int(queue.size()); k++) {
- a = queue[k].first.first;
- b = queue[k].first.second;
- cur = queue[k].second;
- if (x_fin == a && y_fin == b)
- ans = cur;
- if (a+p < m && b+q < n && (!was[a+p][b+q])) {
- queue.emplace_back(make_pair(a + p, b + q), cur + 1);
- was[a + p][b + q] = true;
- }
- if (a+p < m && b-q >= 0 && (!was[a+p][b-q])) {
- queue.emplace_back(make_pair(a + p, b - q), cur + 1);
- was[a + p][b - q] = true;
- }
- if (a-p >= 0 && b+q < n && (!was[a-p][b+q])) {
- queue.emplace_back(make_pair(a - p, b + q), cur + 1);
- was[a - p][b + q] = true;
- }
- if (a-p >= 0 && b-q >= 0 && (!was[a-p][b-q])) {
- queue.emplace_back(make_pair(a - p, b - q), cur + 1);
- was[a - p][b - q] = true;
- }
- if (a+q < m && b+p < n && (!was[a+q][b+p])) {
- queue.emplace_back(make_pair(a + q, b + p), cur + 1);
- was[a + q][b + p] = true;
- }
- if (a+q < m && b-p >= 0 && (!was[a+q][b-p])) {
- queue.emplace_back(make_pair(a + q, b - p), cur + 1);
- was[a + q][b - p] = true;
- }
- if (a-q >= 0 && b+p < n && (!was[a-q][b+p])) {
- queue.emplace_back(make_pair(a - q, b + p), cur + 1);
- was[a - q][b + p] = true;
- }
- if (a-q >= 0 && b-p >= 0 && (!was[a-q][b-p])) {
- queue.emplace_back(make_pair(a - q, b - p), cur + 1);
- was[a - q][b - p] = true;
- }
- }
- }
- int main() {
- int x, y, cur_x, cur_y, cur_ans, i, j;
- cin >> m >> n >> p >> q >> x >> y >> x_fin >> y_fin;
- x_fin--;
- y_fin--;
- for (i = 0; i < m; i++)
- for (j = 0; j < n; j++)
- was[i][j] = false;
- bfs(x-1, y-1);
- if (ans == INT_MAX/2)
- cout << -1;
- else {
- cout << ans << endl;
- for (i = int(queue.size()) - 1; i >= 0; i--)
- if (queue[i].first.first == x_fin && queue[i].first.second == y_fin) {
- path.emplace_back(x_fin, y_fin);
- break;
- }
- cur_x = x_fin;
- cur_y = y_fin;
- cur_ans = ans;
- for (j = i; j >= 0; j--) {
- if (abs(queue[j].first.first - cur_x) == p && abs(queue[j].first.second - cur_y) == q &&
- queue[j].second == cur_ans - 1) {
- path.emplace_back(queue[j].first.first, queue[j].first.second);
- cur_x = queue[j].first.first;
- cur_y = queue[j].first.second;
- cur_ans = queue[j].second;
- } else if (abs(queue[j].first.first - cur_x) == q && abs(queue[j].first.second - cur_y) == p &&
- queue[j].second == cur_ans - 1) {
- path.emplace_back(queue[j].first.first, queue[j].first.second);
- cur_x = queue[j].first.first;
- cur_y = queue[j].first.second;
- cur_ans = queue[j].second;
- }
- }
- reverse(path.begin(), path.end());
- for (i = 0; i < int(path.size()); i++)
- cout << path[i].first+1 << " " << path[i].second+1 << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement