Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<queue>
- #include <iostream>
- #include <climits>
- #include <algorithm>
- using namespace std;
- int PredA[10][10]; // Путь в точку
- int PredB[10][10];
- int A[10][10]; // Счетчик длины пути
- int B[10][10];
- int midx[] = { -1, -1, 1, 1, -2, -2, 2, 2 }; // Варианты ходов коня (по х и у - они связаны)
- int midy[] = { 2, -2, 2, -2, 1, -1, 1, -1 };
- int main()
- {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int x1, x2, y1, y2, a, b;
- a = -1;
- b = -1;
- cin >> x1 >> y1 >> x2 >> y2;
- x1--;
- y1--;
- x2--;
- y2--;
- for (int i = 0; i < 8; i++)
- {
- for (int j = 0; j < 8; j++)
- {
- A[i][j] = INT_MAX;
- }
- }
- for (int i = 0; i < 8; i++)
- {
- for (int j = 0; j < 8; j++)
- {
- B[i][j] = INT_MAX;
- }
- }
- bool flag = false;
- PredA[x1][y1] = -1;
- PredB[x2][y2] = -1;
- A[x1][y1] = 0;
- B[x2][y2] = 0;
- queue <int> q;
- q.push(1000 * x1 + 100 * y1 + 10 * x2 + y2);
- while (!q.empty())
- {
- int c = q.front();
- q.pop();
- int xx1 = c / 1000;
- int yy1 = (c - xx1 * 1000) / 100;
- int xx2 = (c - xx1 * 1000 - yy1 * 100) / 10;
- int yy2 = c % 10;
- if ((xx1 == xx2) && (yy1 == yy2))
- {
- flag = true;
- a = xx1;
- b = yy1;
- break;
- }
- for (int i = 0; i < 8; i++)
- {
- if (xx1 + midx[i] >= 0 && xx1 + midx[i] < 8 && yy1 + midy[i] >= 0 && yy1 + midy[i] < 8)
- {
- if (A[xx1][yy1] + 1 < A[xx1 + midx[i]][yy1 + midy[i]])
- {
- for (int j = 0; j < 8; j++)
- {
- if (xx2 + midx[j] >= 0 && xx2 + midx[j] < 8 && yy2 + midy[j] >= 0 && yy2 + midy[j] < 8)
- {
- if (A[xx2][yy2] + 1 < A[xx2 + midx[j]][yy2 + midy[j]])
- {
- q.push(1000 * xx1 + 100 * yy1 + 10 * xx2 + yy2);
- A[xx1 + midx[i]][yy1 + midy[i]] = A[xx1][yy1] + 1;
- B[xx2 + midx[j]][yy2 + midy[j]] = B[xx2][yy2] + 1;
- PredA[xx1 + midx[i]][yy1 + midy[i]] = xx1 * 10 + yy1;// номер вершины, из которой попали в текущую
- PredB[xx2 + midx[j]][yy2 + midy[j]] = xx2 * 10 + yy2;
- }
- }
- }
- }
- }
- }
- }
- cout << a << " " << b << endl << A[a][b] << " " << B[a][b];
- /*
- if (A[x2][y2] == INT_MAX)
- {
- cout << -1;
- }
- else
- {
- cout << A[x2][y2] << endl;
- vector<pair<int, int>> path;
- pair<int, int> v;
- for (v = Pred[x2][y2]; v != make_pair(-1, -1); v = Pred[v.first][v.second])
- {
- path.push_back(v);
- }
- reverse(path.begin(), path.end());
- for (int i = 0; i < path.size(); i++) // Вывод кратчайшего пути
- {
- cout << path[i].first + 1 << " " << path[i].second + 1 << endl;
- }
- cout << x2 + 1 << " " << y2 + 1 << endl;
- }
- */
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement