Hydron

Один Конь

Dec 8th, 2021
916
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /// https://informatics.msk.ru/mod/statements/view3.php?chapterid=161#1
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. const int DIM = 21;
  7.  
  8. int n, fx, fy, sx, sy, used[DIM][DIM], dist[DIM][DIM];
  9. pair < int, int > from[DIM][DIM]; /// Масив пар цілих чисел для відновлення шляху
  10. queue < pair < int, int > > q; /// Черга, кожен елемент якої - пара цілих чисел
  11.  
  12. void check(int fromx, int fromy, int x, int y){
  13.     if (x > 0 && y > 0 && x <= n && y <= n && used[x][y] == 0){ /// Якщо (х, у) не виходить за межі дошки і якщо вона ще не була відвідана
  14.         used[x][y] = 1;
  15.         dist[x][y] = dist[fromx][fromy] + 1;
  16.         from[x][y] = {fromx, fromy}; /// Попередником точки (х, у) стає точка (fromx, fromy)
  17.         q.push({x, y}); /// Додаємо (х, у) в чергу для подальшого опрацювання
  18.     }
  19. }
  20.  
  21. int main(){
  22.     cin >> n >> fx >> fy >> sx >> sy;
  23.     /**
  24.         Щоб не реверсити відповідь в кінці, можна починати не зі стартової кітинки, а з останньої.
  25.     **/
  26.     q.push({sx, sy}); /// Додаємо в чергу стартову вершину (х2, у2)
  27.     used[sx][sy] = 1;
  28.     while(!q.empty()){
  29.         pair<int,int> v = q.front();
  30.         q.pop();
  31.         check(v.first, v.second, v.first+2, v.second+1); /// v.first - координата точки з черги по х, v.second - координата по у
  32.         check(v.first, v.second, v.first+2, v.second-1);
  33.  
  34.         check(v.first, v.second, v.first-2, v.second+1);
  35.         check(v.first, v.second, v.first-2, v.second-1);
  36.  
  37.         check(v.first, v.second, v.first+1, v.second+2);
  38.         check(v.first, v.second, v.first+1, v.second-2);
  39.  
  40.         check(v.first, v.second, v.first-1, v.second+2);
  41.         check(v.first, v.second, v.first-1, v.second-2);
  42.     }
  43.     cout << dist[fx][fy] << endl;
  44.     while(fx != 0 && fy != 0){
  45.         cout << fx << ' ' << fy << endl;
  46.         pair<int,int> v = from[fx][fy];
  47.         fx = v.first;
  48.         fy = v.second;
  49.     }
  50.     return 0;
  51. }
  52. /*
  53. Breadth First Search
  54. */
  55.  
RAW Paste Data