Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int visited[1001][1001][4][2];
- struct vertex {
- int number;
- int parent;
- int x, y;
- int direction; //up right down left
- int lastTurn;// left none right
- bool super;
- vertex(int number, int parent, int x, int y, int direction, int lastTurn, bool s = false) : number(number), parent(parent), x(x),
- y(y), direction(direction),
- lastTurn(lastTurn), super(s) {}
- vertex() {}
- long long hash() {
- return ((x * 1001 + y) * 100 + direction * 10 + lastTurn) * 1000000 + parent;
- }
- };
- int main() {
- 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++)
- visited[ia][ib][ic][id] = 0;
- int ns, ms, x1, y1, x2, y2;
- 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 >> x1 >> y1 >> x2 >> y2;
- vector<vertex> vertexes;
- vertexes.emplace_back(0, -1, x1, y1, 0, 1);
- vertexes.emplace_back(1, -1, x1, y1, 1, 1);
- vertexes.emplace_back(2, -1, x1, y1, 2, 1);
- vertexes.emplace_back(3, -1, x1, y1, 3, 1);
- vertexes.emplace_back(4, -1, x1, y1, 0, -1);
- vertexes.emplace_back(5, -1, x1, y1, 1, -1);
- vertexes.emplace_back(6, -1, x1, y1, 2, -1);
- vertexes.emplace_back(7, -1, x1, y1, 3, -1);
- visited[x1][y1][0][0] = 1;
- visited[x1][y1][1][0] = 1;
- visited[x1][y1][2][0] = 1;
- visited[x1][y1][3][0] = 1;
- visited[x1][y1][0][1] = 1;
- visited[x1][y1][1][1] = 1;
- visited[x1][y1][2][1] = 1;
- visited[x1][y1][3][1] = 1;
- int sz = 8;
- queue<vertex> q;
- q.push({0, -1, x1, y1, 0, 1});
- q.push({1, -1, x1, y1, 1, 1});
- q.push({2, -1, x1, y1, 2, 1});
- q.push({3, -1, x1, y1, 3, 1});
- q.push({4, -1, x1, y1, 0, -1});
- q.push({5, -1, x1, y1, 1, -1});
- q.push({6, -1, x1, y1, 2, -1});
- q.push({7, -1, x1, y1, 3, -1});
- vertex top_vertex;
- while(!q.empty()) {
- top_vertex = q.front();
- //cout << top_vertex.x << " " << top_vertex.y << " " << top_vertex.direction << endl;
- q.pop();
- if (top_vertex.x == 5 && top_vertex.y == 5) {
- int x;
- x++;
- }
- if (top_vertex.x == x2 && top_vertex.y == y2) {
- break;
- }
- vertex tmp;
- if (!top_vertex.super) {
- if (top_vertex.lastTurn == -1) {
- if (!visited[top_vertex.x][top_vertex.y][(top_vertex.direction + 1) % 4][1]) {
- tmp = {sz++, top_vertex.number, top_vertex.x, top_vertex.y,
- (top_vertex.direction + 1) % 4,
- 1, true};
- vertexes.emplace_back(tmp);
- q.push(vertexes[sz - 1]);
- }
- }
- if (top_vertex.lastTurn == 1) {
- if (!visited[top_vertex.x][top_vertex.y][(top_vertex.direction + 3) % 4][0]) {
- tmp = {sz++, top_vertex.number, top_vertex.x, top_vertex.y,
- (top_vertex.direction + 3) % 4,
- -1, true};
- vertexes.emplace_back(tmp);
- q.push(vertexes[sz - 1]);
- }
- }
- if (!visited[top_vertex.x][top_vertex.y][(top_vertex.direction + 2) % 4][(top_vertex.lastTurn + 1) / 2]) {
- tmp = {sz++, top_vertex.number, top_vertex.x, top_vertex.y,
- (top_vertex.direction + 2) % 4,
- top_vertex.lastTurn, true};
- vertexes.emplace_back(tmp);
- q.push(vertexes[sz - 1]);
- }
- }
- if (top_vertex.direction == 0) {
- if (field[top_vertex.x - 1][top_vertex.y] > 0) {
- if (!visited[top_vertex.x - 1][top_vertex.y][top_vertex.direction][(top_vertex.lastTurn + 1) / 2]) {
- tmp = {sz++, top_vertex.number, top_vertex.x - 1, top_vertex.y,
- top_vertex.direction,
- top_vertex.lastTurn};
- vertexes.emplace_back(tmp);
- q.push(vertexes[sz - 1]);
- visited[top_vertex.x - 1][top_vertex.y][top_vertex.direction][(top_vertex.lastTurn + 1) / 2] = 1;
- }
- }
- }
- if (top_vertex.direction == 1) {
- if (field[top_vertex.x][top_vertex.y + 1] > 0) {
- if (!visited[top_vertex.x][top_vertex.y + 1][top_vertex.direction][(top_vertex.lastTurn + 1) / 2]) {
- tmp = {sz++, top_vertex.number, top_vertex.x, top_vertex.y + 1,
- top_vertex.direction,
- top_vertex.lastTurn};
- vertexes.emplace_back(tmp);
- q.push(vertexes[sz - 1]);
- visited[top_vertex.x][top_vertex.y + 1][top_vertex.direction][(top_vertex.lastTurn + 1) / 2] = 1;
- }
- }
- }
- if (top_vertex.direction == 2) {
- if (field[top_vertex.x + 1][top_vertex.y] > 0) {
- if (!visited[top_vertex.x + 1][top_vertex.y][top_vertex.direction][(top_vertex.lastTurn + 1) / 2]) {
- tmp = {sz++, top_vertex.number, top_vertex.x + 1, top_vertex.y,
- top_vertex.direction,
- top_vertex.lastTurn};
- vertexes.emplace_back(tmp);
- q.push(vertexes[sz - 1]);
- visited[top_vertex.x + 1][top_vertex.y][top_vertex.direction][(top_vertex.lastTurn + 1) / 2] = 1;
- }
- }
- }
- if (top_vertex.direction == 3) {
- if (field[top_vertex.x][top_vertex.y - 1] > 0) {
- if (!visited[top_vertex.x][top_vertex.y - 1][top_vertex.direction][(top_vertex.lastTurn + 1) / 2]) {
- tmp = {sz++, top_vertex.number, top_vertex.x, top_vertex.y - 1,
- top_vertex.direction,
- top_vertex.lastTurn};
- vertexes.emplace_back(tmp);
- q.push(vertexes[sz - 1]);
- visited[top_vertex.x][top_vertex.y - 1][top_vertex.direction][(top_vertex.lastTurn + 1) / 2] = 1;
- }
- }
- }
- }
- vector<pair<int,int>> ansf, anss;
- if (top_vertex.x == x2 && top_vertex.y == y2) {
- do {
- ansf.emplace_back(top_vertex.x, top_vertex.y);
- 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 << x1 << " " << x2 << 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