Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. #include <utility>
  6.  
  7.  
  8. std::pair<int, int> start, endd;
  9.  
  10. enum {
  11.     DOWN,
  12.     LEFT,
  13.     UP,
  14.     RIGHT,
  15. };
  16.  
  17. struct Turns {
  18.     int xx;
  19.     int yy;
  20.     int prev;
  21. };
  22.  
  23. struct Cond {
  24.     int xx;
  25.     int yy;
  26.     int dir;
  27.     int rot;
  28.  
  29.     Cond(int x_p, int y_p, int d_p, int r_p)
  30.             : xx(x_p), yy(y_p), dir(d_p), rot(r_p) {
  31.     }
  32. };
  33.  
  34. int GetDirection(int xx, int yy) {
  35.     if (xx == -1)
  36.         return UP;
  37.     if (xx == 1)
  38.         return DOWN;
  39.     if (yy == 1)
  40.         return RIGHT;
  41.     if (yy == -1)
  42.         return LEFT;
  43.     return 0;
  44. }
  45.  
  46. void update(std::vector<std::vector<std::vector<std::pair<int, int>>>> &used, std::queue<Cond> &qq,
  47.             std::vector<std::vector<std::vector<int>>> &dd,
  48.             std::vector<std::vector<std::vector<Turns>>> &parent,
  49.             Cond &cur, int x1x, int y1y) {
  50.     int xxx = cur.xx;
  51.     int yyy = cur.yy;
  52.     Cond to_push(xxx + x1x, yyy + y1y, GetDirection(x1x, y1y), cur.rot);
  53.  
  54.     if ((to_push.dir - cur.dir + 4) % 4 == 1) {
  55.         to_push.rot = RIGHT;
  56.         if (cur.rot == RIGHT)
  57.             return;
  58.     }
  59.  
  60.     if ((to_push.dir - cur.dir + 4) % 4 == 3) {
  61.         to_push.rot = LEFT;
  62.         if (cur.rot == LEFT)
  63.             return;
  64.     }
  65.  
  66.     if (used[xxx + x1x][yyy + y1y][to_push.dir].first == false &&
  67.     (to_push.rot == LEFT || to_push.rot == 0)) {
  68.         used[xxx + x1x][yyy + y1y][to_push.dir].first = true;
  69.         dd[xxx + x1x][yyy + y1y][to_push.dir + 5 * to_push.rot] =
  70.                 dd[xxx][yyy][cur.dir + 5 * cur.rot] + 1;
  71.         qq.push(to_push);
  72.         parent[xxx + x1x][yyy + y1y][to_push.dir + 5 * to_push.rot] =
  73.                 {xxx, yyy, cur.dir + 5 * cur.rot};
  74.     }
  75.  
  76.     if (used[xxx + x1x][yyy + y1y][to_push.dir].second == false &&
  77.     (to_push.rot == RIGHT || to_push.rot == 0)) {
  78.         used[xxx + x1x][yyy + y1y][to_push.dir].second = true;
  79.         dd[xxx + x1x][yyy + y1y][to_push.dir + 5 * to_push.rot] =
  80.                 dd[xxx][yyy][cur.dir + 5 * cur.rot] + 1;
  81.         qq.push(to_push);
  82.         parent[xxx + x1x][yyy + y1y][to_push.dir + 5 * to_push.rot] =
  83.                 {xxx, yyy, cur.dir + 5 * cur.rot};
  84.     }
  85. }
  86.  
  87. std::vector<std::vector<std::vector<Turns>>>
  88. bfs(std::vector<std::vector<int>> &gg, std::pair<int, int> start, int *mi, int *num) {
  89.     int nn = gg.size();
  90.     int mm = gg[0].size();
  91.     std::vector<std::vector<std::vector<std::pair<int, int>>>> used(nn,
  92.             std::vector<std::vector<std::pair<int, int>>>(mm,
  93.                     std::vector<std::pair<int, int>>(
  94.                             25, {0, 0})));
  95.     std::vector<std::vector<std::vector<Turns>>> parent(nn,
  96.                                                         std::vector<std::vector<Turns>>(mm,
  97.                                                                 std::vector<Turns>(25)));
  98.     std::vector<std::vector<std::vector<int>>> dd(nn, std::vector<std::vector<int>>(mm,
  99.             std::vector<int>(25, -1)));
  100.     std::queue<Cond> qq;
  101.  
  102.     for (int i = 0; i < 4; ++i) {
  103.         used[start.first][start.second][i].first = true;
  104.         used[start.first][start.second][i].second = true;
  105.     }
  106.  
  107.     qq.push(Cond(start.first, start.second, UP, 0));
  108.     qq.push(Cond(start.first, start.second, DOWN, 0));
  109.     qq.push(Cond(start.first, start.second, LEFT, 0));
  110.     qq.push(Cond(start.first, start.second, RIGHT, 0));
  111.  
  112.     while (!qq.empty()) {
  113.         Cond cur = qq.front();
  114.         qq.pop();
  115.         int xxxx = cur.xx;
  116.         int yyyy = cur.yy;
  117.         if (xxxx + 1 < nn && gg[xxxx + 1][yyyy])
  118.             update(used, qq, dd, parent, cur, 1, 0);
  119.         if (xxxx > 0 && gg[xxxx - 1][yyyy])
  120.             update(used, qq, dd, parent, cur, -1, 0);
  121.         if (yyyy + 1 < mm && gg[xxxx][yyyy + 1])
  122.             update(used, qq, dd, parent, cur, 0, 1);
  123.         if (yyyy > 0 && gg[xxxx][yyyy - 1])
  124.             update(used, qq, dd, parent, cur, 0, -1);
  125.     }
  126.  
  127.     for (int i = 0; i < 25; ++i) {
  128.         if (dd[endd.first][endd.second][i] <= *mi && dd[endd.first][endd.second][i] != -1) {
  129.             *mi = dd[endd.first][endd.second][i];
  130.             *num = i;
  131.         }
  132.     }
  133.     return parent;
  134. }
  135.  
  136.  
  137. int main() {
  138.     int n_n = 0, m_m = 0;
  139.     int unused;
  140.     unused = scanf("%d %d", &n_n, &m_m);
  141.     std::vector<std::vector<int>> ggg(n_n, std::vector<int>(m_m));
  142.     getchar();
  143.     for (int i = 0; i < n_n; ++i) {
  144.         for (int l = 0; l < m_m; ++l) {
  145.             (getchar() == '#') ? (ggg[i][l] = 0) : (ggg[i][l] = 1);
  146.         }
  147.         getchar();
  148.     }
  149.     unused = scanf("%d %d", &(start.first), &(start.second));
  150.     unused = scanf("%d %d", &(endd.first), &(endd.second));
  151.  
  152.     (void)unused;
  153.     start.first--;
  154.     start.second--;
  155.     endd.first--;
  156.     endd.second--;
  157.     int res = 999999;
  158.     int num = -1;
  159.     std::vector<std::vector<std::vector<Turns>>> path = bfs(ggg, start, &res, &num);
  160.  
  161.     if (start.first == endd.first && start.second == endd.second) {
  162.         printf("0");
  163.     } else {
  164.         if (num == -1) {
  165.             printf("-1");
  166.         } else {
  167.             printf("%d\n", res + 1);
  168.             std::vector<std::pair<int, int>> result;
  169.             result.push_back(endd);
  170.             Turns current = path[endd.first][endd.second][num];
  171.             for (int i = res + 1; i > 0; --i) {
  172.                 std::pair<int, int> tmp(current.xx, current.yy);
  173.                 result.push_back(tmp);
  174.                 current = path[current.xx][current.yy][current.prev];
  175.             }
  176.             reverse(result.begin(), result.end());
  177.             for (int i = 0; i < res + 2; ++i) {
  178.                 printf("%d %d\n", result[i].first + 1, result[i].second + 1);
  179.             }
  180.         }
  181.     }
  182.  
  183.     return 0;
  184. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement