SHARE
TWEET

Untitled

Kekulidze Jan 21st, 2020 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3.  
  4. using namespace std;
  5. struct Position
  6. {
  7.     int x;
  8.     int y;
  9. };
  10. int n, m;
  11. Position  parents[21][21];
  12. bool used[21][21];
  13. queue<Position> q;
  14.  
  15. bool Check(int x, int y)
  16. {
  17.     if (x >= 1 && x <= m && y >= 1 && y <= m)
  18.         return true;
  19.     else return false;
  20. }
  21. void proc(Position u, int x, int y, int** dist)
  22. {
  23.     if (Check(x, y) && !used[y][x])
  24.     {
  25.         used[y][x] = true;
  26.         parents[y][x] = u;
  27.         dist[y][x] = dist[u.y][u.x] + 1;
  28.         Position v = { x,y };
  29.         q.push(v);
  30.  
  31.     }
  32.  
  33. }
  34. void BFS(Position start, int** dist) {
  35.     used[start.y][start.x] = true;
  36.     parents[start.y][start.x] = start;
  37.     dist[start.y][start.x] = 0;
  38.     Position u{ start.x,start.y };
  39.     q.push(u);
  40.     while (!q.empty()) {
  41.         u = q.front();
  42.         q.pop();
  43.  
  44.         proc(u, u.x - 1, u.y - 2, dist);
  45.         proc(u, u.x - 1, u.y + 2, dist);
  46.         proc(u, u.x - 2, u.y - 1, dist);
  47.         proc(u, u.x - 2, u.y + 1, dist);
  48.         proc(u, u.x + 1, u.y - 2, dist);
  49.         proc(u, u.x + 1, u.y + 2, dist);
  50.         proc(u, u.x + 2, u.y - 1, dist);
  51.         proc(u, u.x + 2, u.y + 1, dist);
  52.  
  53.  
  54.  
  55.     }
  56. }
  57.  
  58. void print_way(Position u)
  59. {
  60.     if (parents[u.y][u.x].x != u.x || parents[u.y][u.x].y != u.y)
  61.     {
  62.         print_way(parents[u.y][u.x]);
  63.     }
  64.     cout << u.x << ' ' << u.y << endl;
  65. }
  66. int main()
  67. {
  68.     freopen("input.txt", "r", stdin);
  69.     freopen("output.txt", "w", stdout);
  70.  
  71.  
  72.     cin >> n >> m;
  73.  
  74.     Position start, end;
  75.     int** dist = new int* [21];
  76.     for (int i = 1; i <= 21; i++)
  77.         dist[i] = new int[21];
  78.     cin >> start.x >> start.y;
  79.     cin >> end.x >> end.y;
  80.     BFS(start, dist);
  81.  
  82.  
  83.     if (dist[end.y][end.x] > 0)
  84.     {
  85.         cout << dist[end.y][end.x] << endl;
  86.         print_way(end);
  87.  
  88.  
  89.     }
  90.     else if (dist[end.y][end.x] == 0)
  91.         cout << 0 << endl << end.x<<" "<<end.y;
  92.     else cout <<-1;
  93.  
  94.  
  95.  
  96. }
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