Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2020
241
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.67 KB | None | 0 0
  1. #include<queue>
  2. #include <iostream>
  3. #include <climits>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int PredA[10][10];  // Путь в точку
  8. int PredB[10][10];
  9. int A[10][10]; // Счетчик длины пути
  10. int B[10][10];
  11. int midx[] = { -1, -1, 1, 1, -2, -2, 2, 2 }; // Варианты ходов коня (по х и у - они связаны)
  12. int midy[] = { 2, -2, 2, -2, 1, -1, 1, -1 };
  13.  
  14.  
  15. int main()
  16. {
  17.     freopen("input.txt", "r", stdin);
  18.     freopen("output.txt", "w", stdout);
  19.     int x1, x2, y1, y2, a, b;
  20.     a = -1;
  21.     b = -1;
  22.     cin >> x1 >> y1 >> x2 >> y2;
  23.     x1--;
  24.     y1--;
  25.     x2--;
  26.     y2--;
  27.     for (int i = 0; i < 8; i++)
  28.     {
  29.         for (int j = 0; j < 8; j++)
  30.         {
  31.             A[i][j] = INT_MAX;
  32.         }
  33.     }
  34.     for (int i = 0; i < 8; i++)
  35.     {
  36.         for (int j = 0; j < 8; j++)
  37.         {
  38.             B[i][j] = INT_MAX;
  39.         }
  40.     }
  41.  
  42.     bool flag = false;
  43.     PredA[x1][y1] = -1;
  44.     PredB[x2][y2] = -1;
  45.     A[x1][y1] = 0;
  46.     B[x2][y2] = 0;
  47.     queue <int> q;
  48.     q.push(1000 * x1 + 100 * y1 + 10 * x2 + y2);
  49.     while (!q.empty())
  50.     {
  51.         int c = q.front();
  52.         q.pop();
  53.         int xx1 = c / 1000;
  54.         int yy1 = (c - xx1 * 1000) / 100;
  55.         int xx2 = (c - xx1 * 1000 - yy1 * 100) / 10;
  56.         int yy2 = c % 10;
  57.  
  58.         if ((xx1 == xx2) && (yy1 == yy2))
  59.         {
  60.             flag = true;
  61.             a = xx1;
  62.             b = yy1;
  63.             break;
  64.         }
  65.        
  66.        
  67.         for (int i = 0; i < 8; i++)
  68.         {
  69.             if (xx1 + midx[i] >= 0 && xx1 + midx[i] < 8 && yy1 + midy[i] >= 0 && yy1 + midy[i] < 8)
  70.             {
  71.                 if (A[xx1][yy1] + 1 < A[xx1 + midx[i]][yy1 + midy[i]])
  72.                 {
  73.                     for (int j = 0; j < 8; j++)
  74.                     {
  75.                         if (xx2 + midx[j] >= 0 && xx2 + midx[j] < 8 && yy2 + midy[j] >= 0 && yy2 + midy[j] < 8)
  76.                         {
  77.                             if (A[xx2][yy2] + 1 < A[xx2 + midx[j]][yy2 + midy[j]])
  78.                             {
  79.                                 q.push(1000 * xx1 + 100 * yy1 + 10 * xx2 + yy2);
  80.                                 A[xx1 + midx[i]][yy1 + midy[i]] = A[xx1][yy1] + 1;
  81.                                 B[xx2 + midx[j]][yy2 + midy[j]] = B[xx2][yy2] + 1;
  82.                                 PredA[xx1 + midx[i]][yy1 + midy[i]] = xx1 * 10 + yy1;// номер вершины, из которой попали в текущую
  83.                                 PredB[xx2 + midx[j]][yy2 + midy[j]] = xx2 * 10 + yy2;
  84.                             }
  85.                         }
  86.                     }
  87.                 }
  88.             }
  89.         }
  90.     }
  91.     cout << a << " " << b << endl << A[a][b] << " " << B[a][b];
  92.     /*
  93.     if (A[x2][y2] == INT_MAX)
  94.     {
  95.         cout << -1;
  96.     }
  97.     else
  98.     {
  99.         cout << A[x2][y2] << endl;
  100.        
  101.         vector<pair<int, int>> path;
  102.         pair<int, int> v;
  103.         for (v = Pred[x2][y2]; v != make_pair(-1, -1); v = Pred[v.first][v.second])
  104.         {
  105.             path.push_back(v);
  106.         }
  107.         reverse(path.begin(), path.end());
  108.  
  109.         for (int i = 0; i < path.size(); i++) // Вывод кратчайшего пути
  110.         {
  111.             cout << path[i].first + 1 << " " << path[i].second + 1 << endl;
  112.         }
  113.         cout << x2 + 1 << " " << y2 + 1 << endl;
  114.     }
  115.     */
  116.     return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement