Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <string>
- #include <sstream>
- #include <queue>
- #include <utility>
- using std::vector;
- using std::cin;
- using std::cout;
- using std::queue;
- using std::pair;
- using std::endl;
- int visited[1001][1001][4][2][2];
- struct vertex {
- int number;
- int parent;
- int xx, yy;
- int direction; // up right down left
- int lastTurn; // left none right
- bool super;
- vertex(int number, int parent, int xx, int yy,
- int direction, int lastTurn, bool ss = false) : number(number),
- parent(parent), xx(xx),
- yy(yy),
- direction(direction),
- lastTurn(lastTurn),
- super(ss) {}
- vertex() {}
- };
- int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
- for (int ia = 0; ia < 1001; ++ia)
- for (int ib = 0; ib < 1001; ++ib)
- for (int ic = 0; ic < 4; ++ic)
- for (int id = 0; id < 2; ++id)
- for(int ie = 0; ie < 2; ++ie)
- visited[ia][ib][ic][id][ie] = 0;
- int ns, ms, x_first, y_first, x_second, y_second;
- cin >> ns >> ms;
- vector<vector<int>> field(ns + 2, vector<int>(ms + 2, 0));
- char c = '.';
- for (int i = 1; i <= ns; ++i) {
- for (int j = 1; j <= ms; ++j) {
- cin >> c;
- if (c == '.') {
- field[i][j] = 1;
- }
- }
- }
- cin >> x_first >> y_first >> x_second >> y_second;
- if (x_first == x_second && y_first == y_second) {
- cout << 0 << endl << x_first << " " << x_second;
- return 0;
- }
- vector<vertex> vertexes;
- vertexes.emplace_back(0, -1, x_first, y_first, 0, 1);
- vertexes.emplace_back(1, -1, x_first, y_first, 1, 1);
- vertexes.emplace_back(2, -1, x_first, y_first, 2, 1);
- vertexes.emplace_back(3, -1, x_first, y_first, 3, 1);
- vertexes.emplace_back(4, -1, x_first, y_first, 0, -1);
- vertexes.emplace_back(5, -1, x_first, y_first, 1, -1);
- vertexes.emplace_back(6, -1, x_first, y_first, 2, -1);
- vertexes.emplace_back(7, -1, x_first, y_first, 3, -1);
- visited[x_first][y_first][0][0][0] = 1;
- visited[x_first][y_first][1][0][0] = 1;
- visited[x_first][y_first][2][0][0] = 1;
- visited[x_first][y_first][3][0][0] = 1;
- visited[x_first][y_first][0][1][0] = 1;
- visited[x_first][y_first][1][1][0] = 1;
- visited[x_first][y_first][2][1][0] = 1;
- visited[x_first][y_first][3][1][0] = 1;
- int sz = 8;
- queue<vertex> q;
- q.push({0, -1, x_first, y_first, 0, 1});
- q.push({1, -1, x_first, y_first, 1, 1});
- q.push({2, -1, x_first, y_first, 2, 1});
- q.push({3, -1, x_first, y_first, 3, 1});
- q.push({4, -1, x_first, y_first, 0, -1});
- q.push({5, -1, x_first, y_first, 1, -1});
- q.push({6, -1, x_first, y_first, 2, -1});
- q.push({7, -1, x_first, y_first, 3, -1});
- vertex top_vertex;
- while (!q.empty()) {
- top_vertex = q.front();
- // cout << top_vertex.xx << " " << top_vertex.y << " " << top_vertex.direction << endl;
- q.pop();
- if (top_vertex.xx == x_second && top_vertex.yy == y_second) {
- break;
- }
- vertex tmptea;
- if (!top_vertex.super) {
- if (top_vertex.lastTurn == -1) {
- if (!visited[top_vertex.xx][top_vertex.yy][(top_vertex.direction + 1) % 4][1][1]) {
- tmptea = {sz++, top_vertex.number, top_vertex.xx, top_vertex.yy,
- (top_vertex.direction + 1) % 4,
- 1, true};
- vertexes.emplace_back(tmptea);
- q.push(vertexes[sz - 1]);
- visited[top_vertex.xx][top_vertex.yy][(top_vertex.direction + 1) % 4][1][1] = 1;
- }
- }
- if (top_vertex.lastTurn == 1) {
- if (!visited[top_vertex.xx][top_vertex.yy][(top_vertex.direction + 3) % 4][0][1]) {
- tmptea = {sz++, top_vertex.number, top_vertex.xx, top_vertex.yy,
- (top_vertex.direction + 3) % 4,
- -1, true};
- vertexes.emplace_back(tmptea);
- q.push(vertexes[sz - 1]);
- visited[top_vertex.xx][top_vertex.yy][(top_vertex.direction + 3) % 4][0][1] = 1;
- }
- }
- if (!visited[top_vertex.xx][top_vertex.yy][(top_vertex.direction + 2)
- % 4][(top_vertex.lastTurn + 1) / 2][1]) {
- tmptea = {sz++, top_vertex.number, top_vertex.xx, top_vertex.yy,
- (top_vertex.direction + 2) % 4,
- top_vertex.lastTurn, true};
- vertexes.emplace_back(tmptea);
- q.push(vertexes[sz - 1]);
- visited[top_vertex.xx][top_vertex.yy][(top_vertex.direction + 2)
- % 4][(top_vertex.lastTurn + 1) / 2][1] = 1;
- }
- }
- if (top_vertex.direction == 0) {
- if (field[top_vertex.xx - 1][top_vertex.yy] > 0) {
- if (!visited[top_vertex.xx - 1][top_vertex.yy][top_vertex.direction
- ][(top_vertex.lastTurn + 1) / 2][0]) {
- tmptea = {sz++, top_vertex.number, top_vertex.xx - 1, top_vertex.yy,
- top_vertex.direction,
- top_vertex.lastTurn};
- vertexes.emplace_back(tmptea);
- q.push(vertexes[sz - 1]);
- visited[top_vertex.xx - 1][top_vertex.yy][top_vertex.direction
- ][(top_vertex.lastTurn + 1) / 2][0] = 1;
- }
- }
- }
- if (top_vertex.direction == 1) {
- if (field[top_vertex.xx][top_vertex.yy + 1] > 0) {
- if (!visited[top_vertex.xx][top_vertex.yy + 1][top_vertex.direction
- ][(top_vertex.lastTurn + 1) / 2][0]) {
- tmptea = {sz++, top_vertex.number, top_vertex.xx, top_vertex.yy + 1,
- top_vertex.direction,
- top_vertex.lastTurn};
- vertexes.emplace_back(tmptea);
- q.push(vertexes[sz - 1]);
- visited[top_vertex.xx][top_vertex.yy + 1][top_vertex.direction
- ][(top_vertex.lastTurn + 1) / 2][0] = 1;
- }
- }
- }
- if (top_vertex.direction == 2) {
- if (field[top_vertex.xx + 1][top_vertex.yy] > 0) {
- if (!visited[top_vertex.xx + 1][top_vertex.yy][top_vertex.direction
- ][(top_vertex.lastTurn + 1) / 2][0]) {
- tmptea = {sz++, top_vertex.number, top_vertex.xx + 1, top_vertex.yy,
- top_vertex.direction,
- top_vertex.lastTurn};
- vertexes.emplace_back(tmptea);
- q.push(vertexes[sz - 1]);
- visited[top_vertex.xx + 1][top_vertex.yy][top_vertex.direction
- ][(top_vertex.lastTurn + 1) / 2][0] = 1;
- }
- }
- }
- if (top_vertex.direction == 3) {
- if (field[top_vertex.xx][top_vertex.yy - 1] > 0) {
- if (!visited[top_vertex.xx][top_vertex.yy - 1][top_vertex.direction
- ][(top_vertex.lastTurn + 1) / 2][0]) {
- tmptea = {sz++, top_vertex.number, top_vertex.xx, top_vertex.yy - 1,
- top_vertex.direction,
- top_vertex.lastTurn};
- vertexes.emplace_back(tmptea);
- q.push(vertexes[sz - 1]);
- visited[top_vertex.xx][top_vertex.yy - 1][top_vertex.direction
- ][(top_vertex.lastTurn + 1) / 2][0] = 1;
- }
- }
- }
- }
- vector<pair<int, int>> ansf, anss;
- if (top_vertex.xx == x_second && top_vertex.yy == y_second) {
- do {
- ansf.emplace_back(top_vertex.xx, top_vertex.yy);
- if (top_vertex.parent != -1)
- top_vertex = vertexes[top_vertex.parent];
- } while (top_vertex.parent != -1);
- anss.push_back(ansf[ansf.size() - 1]);
- for (int i = ansf.size() - 2; i >= 0; --i) {
- if (ansf[i] != ansf[i + 1]) {
- anss.push_back(ansf[i]);
- }
- }
- cout << anss.size() << endl;
- cout << x_first << " " << x_second << endl;
- for (auto el : anss) {
- cout << el.first << " " << el.second << endl;
- }
- } else {
- cout << -1;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement