Advertisement
Guest User

Untitled

a guest
Apr 4th, 2020
227
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.26 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <string>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #include <cmath>
  8.  
  9. using namespace std;
  10.  
  11. int PosToVertexId(int row, int column, int m) {
  12.     return (row * m) + column;
  13. }
  14.  
  15. pair<int, int> VertexIdToPos(int VertexID, int m) {
  16.     return make_pair(VertexID / m, VertexID % m);
  17. }
  18.  
  19. bool isInside(int x, int y, int n, int m) {
  20.     return 0 <= x && x < n && 0 <= y && y < m;
  21. }
  22.  
  23. void BFS(int s, int e, vector<vector<int>> &adjmatrix) {
  24.     int n = adjmatrix.size(), m = sqrt(n);
  25.     vector<bool> visited(n);
  26.     vector<int> d(n), p(n);
  27.     queue<int> queue;
  28.  
  29.     queue.push(s);
  30.     visited[s] = true;
  31.     p[s] = -1;
  32.     while (!queue.empty()) {
  33.         int v = queue.front();
  34.         queue.pop();
  35.         for (int i = 0; i < adjmatrix.size(); i++) {
  36.             if (adjmatrix[v][i] != 0 && !visited[i]) {
  37.                 visited[i] = true;
  38.                 queue.push(i);
  39.                 d[i] = d[v] + 1;
  40.                 p[i] = v;
  41.             }
  42.         }
  43.     }
  44.  
  45.     if (!visited[e])
  46.         cout << -1;
  47.     else {
  48.         int path_size = d[e];
  49.         if ((path_size ) % 2 == 0) {
  50.             cout << path_size / 2 << endl;
  51.             vector<int> path;
  52.             for (int v = e; v != -1; v = p[v])
  53.                 path.push_back(v);
  54.             reverse(path.begin(), path.end());
  55.             for (int i = 1; i <= path_size / 2; i++) {
  56.                 int Rv = path[i];
  57.                 int Gv = path[path_size - i];
  58.                 pair<int, int> Rcell = VertexIdToPos(Rv, m);
  59.                 pair<int, int> Gcell = VertexIdToPos(Gv, m);
  60.                 cout << Rcell.first + 1 << " " << Rcell.second + 1 << " ";
  61.                 cout << Gcell.first + 1 << " " << Gcell.second + 1 << endl;
  62.             }
  63.         }
  64.         else
  65.             cout << -1;
  66.     }
  67. }
  68.  
  69. int main() {
  70.  
  71.     freopen("input.txt", "r", stdin);
  72.     freopen("output.txt", "w", stdout);
  73.  
  74.     int n = 8, m = 8, x1, y1, x2, y2;
  75.     cin >> x1 >> y1 >> x2 >> y2;
  76.     x1--; y1--; x2--; y2--;
  77.     int x_move[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
  78.     int y_move[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
  79.     vector<vector<int>> matrix(n*m, vector<int>(n*m));
  80.     for (size_t i = 0; i < n*m; i++) {
  81.         for (size_t k = 0; k < 8; k++) {
  82.             int next_i = i / m + x_move[k];
  83.             int next_j = i % m + y_move[k];
  84.             if (isInside(next_i, next_j, n, m))
  85.                 matrix[i][next_i*m + next_j] = 1;
  86.         }
  87.     }
  88.  
  89.     int s = PosToVertexId(x1, y1, m);
  90.     int e = PosToVertexId(x2, y2, m);
  91.  
  92.     if (s == e)
  93.         cout << 0 << endl;
  94.     else
  95.         BFS(s, e, matrix);
  96.  
  97.     return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement