Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <utility>
- std::pair<int, int> start, endd;
- enum {
- DOWN,
- LEFT,
- UP,
- RIGHT,
- };
- struct Turns {
- int xx;
- int yy;
- int prev;
- };
- struct Cond {
- int xx;
- int yy;
- int dir;
- int rot;
- Cond(int x_p, int y_p, int d_p, int r_p)
- : xx(x_p), yy(y_p), dir(d_p), rot(r_p) {
- }
- };
- int GetDirection(int xx, int yy) {
- if (xx == -1)
- return UP;
- if (xx == 1)
- return DOWN;
- if (yy == 1)
- return RIGHT;
- if (yy == -1)
- return LEFT;
- return 0;
- }
- void update(std::vector<std::vector<std::vector<std::pair<int, int>>>> &used, std::queue<Cond> &qq,
- std::vector<std::vector<std::vector<int>>> &dd,
- std::vector<std::vector<std::vector<Turns>>> &parent,
- Cond &cur, int x1x, int y1y) {
- int xxx = cur.xx;
- int yyy = cur.yy;
- Cond to_push(xxx + x1x, yyy + y1y, GetDirection(x1x, y1y), cur.rot);
- if ((to_push.dir - cur.dir + 4) % 4 == 1) {
- to_push.rot = RIGHT;
- if (cur.rot == RIGHT)
- return;
- }
- if ((to_push.dir - cur.dir + 4) % 4 == 3) {
- to_push.rot = LEFT;
- if (cur.rot == LEFT)
- return;
- }
- if (used[xxx + x1x][yyy + y1y][to_push.dir].first == false &&
- (to_push.rot == LEFT || to_push.rot == 0)) {
- used[xxx + x1x][yyy + y1y][to_push.dir].first = true;
- dd[xxx + x1x][yyy + y1y][to_push.dir + 5 * to_push.rot] =
- dd[xxx][yyy][cur.dir + 5 * cur.rot] + 1;
- qq.push(to_push);
- parent[xxx + x1x][yyy + y1y][to_push.dir + 5 * to_push.rot] =
- {xxx, yyy, cur.dir + 5 * cur.rot};
- }
- if (used[xxx + x1x][yyy + y1y][to_push.dir].second == false &&
- (to_push.rot == RIGHT || to_push.rot == 0)) {
- used[xxx + x1x][yyy + y1y][to_push.dir].second = true;
- dd[xxx + x1x][yyy + y1y][to_push.dir + 5 * to_push.rot] =
- dd[xxx][yyy][cur.dir + 5 * cur.rot] + 1;
- qq.push(to_push);
- parent[xxx + x1x][yyy + y1y][to_push.dir + 5 * to_push.rot] =
- {xxx, yyy, cur.dir + 5 * cur.rot};
- }
- }
- std::vector<std::vector<std::vector<Turns>>>
- bfs(std::vector<std::vector<int>> &gg, std::pair<int, int> start, int *mi, int *num) {
- int nn = gg.size();
- int mm = gg[0].size();
- std::vector<std::vector<std::vector<std::pair<int, int>>>> used(nn,
- std::vector<std::vector<std::pair<int, int>>>(mm,
- std::vector<std::pair<int, int>>(
- 25, {0, 0})));
- std::vector<std::vector<std::vector<Turns>>> parent(nn,
- std::vector<std::vector<Turns>>(mm,
- std::vector<Turns>(25)));
- std::vector<std::vector<std::vector<int>>> dd(nn, std::vector<std::vector<int>>(mm,
- std::vector<int>(25, -1)));
- std::queue<Cond> qq;
- for (int i = 0; i < 4; ++i) {
- used[start.first][start.second][i].first = true;
- used[start.first][start.second][i].second = true;
- }
- qq.push(Cond(start.first, start.second, UP, 0));
- qq.push(Cond(start.first, start.second, DOWN, 0));
- qq.push(Cond(start.first, start.second, LEFT, 0));
- qq.push(Cond(start.first, start.second, RIGHT, 0));
- while (!qq.empty()) {
- Cond cur = qq.front();
- qq.pop();
- int xxxx = cur.xx;
- int yyyy = cur.yy;
- if (xxxx + 1 < nn && gg[xxxx + 1][yyyy])
- update(used, qq, dd, parent, cur, 1, 0);
- if (xxxx > 0 && gg[xxxx - 1][yyyy])
- update(used, qq, dd, parent, cur, -1, 0);
- if (yyyy + 1 < mm && gg[xxxx][yyyy + 1])
- update(used, qq, dd, parent, cur, 0, 1);
- if (yyyy > 0 && gg[xxxx][yyyy - 1])
- update(used, qq, dd, parent, cur, 0, -1);
- }
- for (int i = 0; i < 25; ++i) {
- if (dd[endd.first][endd.second][i] <= *mi && dd[endd.first][endd.second][i] != -1) {
- *mi = dd[endd.first][endd.second][i];
- *num = i;
- }
- }
- return parent;
- }
- int main() {
- int n_n = 0, m_m = 0;
- int unused;
- unused = scanf("%d %d", &n_n, &m_m);
- std::vector<std::vector<int>> ggg(n_n, std::vector<int>(m_m));
- getchar();
- for (int i = 0; i < n_n; ++i) {
- for (int l = 0; l < m_m; ++l) {
- (getchar() == '#') ? (ggg[i][l] = 0) : (ggg[i][l] = 1);
- }
- getchar();
- }
- unused = scanf("%d %d", &(start.first), &(start.second));
- unused = scanf("%d %d", &(endd.first), &(endd.second));
- (void)unused;
- start.first--;
- start.second--;
- endd.first--;
- endd.second--;
- int res = 999999;
- int num = -1;
- std::vector<std::vector<std::vector<Turns>>> path = bfs(ggg, start, &res, &num);
- if (start.first == endd.first && start.second == endd.second) {
- printf("0");
- } else {
- if (num == -1) {
- printf("-1");
- } else {
- printf("%d\n", res + 1);
- std::vector<std::pair<int, int>> result;
- result.push_back(endd);
- Turns current = path[endd.first][endd.second][num];
- for (int i = res + 1; i > 0; --i) {
- std::pair<int, int> tmp(current.xx, current.yy);
- result.push_back(tmp);
- current = path[current.xx][current.yy][current.prev];
- }
- reverse(result.begin(), result.end());
- for (int i = 0; i < res + 2; ++i) {
- printf("%d %d\n", result[i].first + 1, result[i].second + 1);
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement