daily pastebin goal
54%
SHARE
TWEET

Untitled

a guest Feb 19th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. struct position {  //заведем структуру из пар для хранения координат
  8.     int x;
  9.     int y;
  10. };
  11.  
  12. position makepair (int x, int y) {
  13.     position pair;
  14.     pair.x = x;
  15.     pair.y = y;
  16.     return pair;
  17. }
  18.  
  19. vector <position> variants (position location) {
  20.     //найдем координаты клеток, в которую может попасть конь из текущей (8 вариантов)
  21.     //(x+2)(y-1) (x+2)(y+1) (x-2)(y-1) (x-2)(y+1) (x+1)(y+2) (x-1)(y+2) (x+1)(y-2) (x+1)(y-2)
  22.     //для перебора данных вариантов создадим два вектора
  23.     vector <int> change_x = {2, 2, 1, 1, -1, -1, -2, -2};
  24.     vector <int> change_y = {1, -1, 2, -2, 2, -2, 1, -1};
  25.     vector <position> newx(8);
  26.     for (int i = 0; i < 8; i++) {
  27.         newx[i].x = location.x + change_x[i];
  28.         newx[i].y = location.y + change_y[i];
  29.     }
  30.     return newx;
  31. }
  32.  
  33. bool check (position g, int size) { //проверка на попадание в рамки доски
  34.     if (g.x > size || g.x < 1 || g.y > size || g.y < 1) return false;
  35.     else return true;
  36. }
  37.  
  38. int main() {
  39.     int N = 8;
  40.     int x1, y1, x2, y2;
  41.     char x_1, x_2;
  42.     cin >> x_1 >> y1 >> x_2 >> y2;
  43.     x1 = x_1 - 96;
  44.     x2 = x_2 - 96;
  45.     if (x1 == x2 && y1 == y2) {
  46.         cout << 0;
  47.         return(0);
  48.     }
  49.     //не забыть проверять на попадание в рамки доски
  50.     position g = makepair(x1, y1);
  51.     queue <position> fire;
  52.     vector <vector <int>> used (N, vector <int> (N));
  53.     vector <position> news;
  54.     vector <vector <position>> parent (N, vector <position> (N, {123, 123}));
  55.     fire.push(g);
  56.     parent[g.x-1][g.y-1] = {-1, -1};
  57.     used[x1-1][y1-1] = 1;
  58.     while (!fire.empty()) {
  59.         position temp = fire.front();
  60.         fire.pop();
  61.         news = variants(temp);
  62.         for (int i = 0; i < 8; i++) {
  63.             if (check(news[i], N) == true && used[news[i].x-1][news[i].y-1] == 0) {
  64.                 used[news[i].x-1][news[i].y-1] = 1;
  65.                 fire.push(news[i]);
  66.                 parent[news[i].x-1][news[i].y-1] = temp;
  67.                 if (news[i].x == x2 && news[i].y == y2) goto lengthcount;
  68.             }
  69.         }
  70.     }
  71.  
  72.     if (parent[x2-1][y2-1].x == 123 && parent[x2-1][y2-1].y == 123) {
  73.         cout << "-1";
  74.         return(0);
  75.     }
  76. lengthcount:
  77.     int length = 0;
  78.     vector <position> path;
  79.     for (position t = makepair(x2, y2); t.x != -1 && t.y != -1; t = parent[t.x - 1][t.y - 1]) {
  80.         length++;
  81.     }
  82.     if ((length - 1) % 2 == 0) cout << length / 2;
  83.     else cout << "-1";
  84. }
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