allia

шахматный конь

Jan 11th, 2021 (edited)
875
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. const int inf = 1000;
  6. struct kletka
  7. {
  8.  int x, y;
  9.  void new_kletka(int x, int y)
  10.  {
  11.    this->x = x;
  12.    this->y = y;
  13.  }
  14. };
  15.  
  16. class Graph
  17. {
  18. public:
  19.     queue<kletka> Q;
  20.     int n, m, dlina = 0, *dx, *dy;
  21.     kletka start, finish, *itog;
  22.     int **arr;
  23.  
  24.     Graph(int N, int M, int x1, int y1, int x2, int y2)
  25.     {
  26.         n = N;
  27.         m = M;
  28.         start.new_kletka(x1, y1);
  29.         finish.new_kletka(x2, y2);
  30.  
  31.         arr = new int*[n];
  32.         for (int i = 0; i < n; i++)
  33.          arr[i] = new int[m];
  34.  
  35.         for(int i = 0; i < n; i++)
  36.          for (int j = 0; j < m; j++)
  37.           arr[i][j] = inf;
  38.      
  39.         arr[x1][y1] = 0;
  40.        
  41.         dx = new int[8]{2, 2, 1, 1, -1, -1, -2, -2};
  42.         dy = new int[8]{1, -1, 2, -2, 2, -2, 1, -1};
  43.     }
  44.  
  45.     void smejnost();
  46.     void all_way();
  47.     void result();
  48.     void negative() { cout << -1;};
  49. };
  50.  
  51. void Graph::smejnost()
  52. {
  53.   int i, j, u = 0, v = 0;
  54.   kletka a;
  55.   Q.push(start);
  56.  
  57.   while(!Q.empty())
  58.   {
  59.    i = Q.front().x;
  60.    j = Q.front().y;
  61.    Q.pop();
  62.  
  63.    for(int k = 0; k < 8; ++k)
  64.     {
  65.       u = i + dx[k];
  66.       v = j + dy[k];
  67.  
  68.       if(u >= 0 && u < n && v >= 0 && v < m && arr[u][v] > arr[i][j] + 1)
  69.       {
  70.        arr[u][v] = arr[i][j] + 1;
  71.        a.new_kletka(u, v);
  72.        Q.push(a);
  73.       }
  74.     }
  75.   }
  76.   dlina = arr[finish.x][finish.y];
  77.   if(dlina == inf)
  78.     negative();
  79.   else
  80.     all_way();
  81. }
  82.  
  83. void Graph::all_way()
  84. {
  85.   kletka a;
  86.   int i = 0, j = 0, u = 0, v = 0, shet = 1;
  87.   itog = new kletka[dlina + 1];
  88.   itog[0] = finish;
  89.  
  90.   Q.push(finish);
  91.  
  92.   while(shet != dlina)
  93.   {
  94.    i = Q.front().x;
  95.    j = Q.front().y;
  96.    Q.pop();
  97.  
  98.    for(int k = 0; k < 8; ++k)
  99.     {
  100.       u = i - dx[k];
  101.       v = j  - dy[k];
  102.  
  103.       if(u >= 0 && u < n && v >= 0 && v < m && arr[u][v] == arr[i][j] - 1)
  104.       {
  105.        a.new_kletka(u, v);
  106.        Q.push(a);
  107.        itog[shet] = a;
  108.        shet++;
  109.        break;
  110.       }
  111.     }
  112.   }
  113.   itog[dlina] = start;
  114.   result();
  115. }
  116.  
  117. void Graph::result()
  118. {
  119.   cout << dlina << endl;
  120.  
  121.   for (int i = dlina; i >= 0; i--)
  122.    cout << itog[i].x + 1 << " " << itog[i].y +1  << endl;
  123. }
  124.  
  125. int main()
  126. {
  127.     int n, m, x1, y1, x2, y2;
  128.     cin >> n >> m;
  129.     cin >> x1 >> y1 >> x2 >> y2;
  130.     Graph object(n, m, x1-1, y1-1, x2-1, y2-1);
  131.     object.smejnost();
  132. }
RAW Paste Data