Advertisement
Guest User

Untitled

a guest
Jan 16th, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.22 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int visited[1001][1001][4][2];
  6.  
  7. struct vertex {
  8.     int number;
  9.     int parent;
  10.     int x, y;
  11.     int direction; //up right down left
  12.     int lastTurn;// left none right
  13.     bool super;
  14.     vertex(int number, int parent, int x, int y, int direction, int lastTurn, bool s = false) : number(number), parent(parent), x(x),
  15.                                                                                 y(y), direction(direction),
  16.                                                                                 lastTurn(lastTurn), super(s) {}
  17.  
  18.     vertex() {}
  19.     long long hash() {
  20.         return ((x * 1001 + y) * 100 + direction * 10 + lastTurn) * 1000000 + parent;
  21.     }
  22.  
  23.  
  24. };
  25.  
  26. int main() {
  27.  
  28.     for (int ia = 0; ia < 1001; ia++)
  29.         for (int ib = 0; ib < 1001; ib++)
  30.             for (int ic = 0; ic < 4; ic++)
  31.                 for (int id = 0; id < 2; id++)
  32.                     visited[ia][ib][ic][id] = 0;
  33.  
  34.     int ns, ms, x1, y1, x2, y2;
  35.     cin >> ns >> ms;
  36.     vector<vector<int>> field(ns + 2, vector<int>(ms + 2, 0));
  37.     char c = '.';
  38.     for (int i = 1; i <= ns; i++) {
  39.         for (int j = 1; j <= ms; j++) {
  40.             cin >> c;
  41.             if (c == '.') {
  42.                 field[i][j] = 1;
  43.             }
  44.         }
  45.     }
  46.     cin >> x1 >> y1 >> x2 >> y2;
  47.  
  48.     vector<vertex> vertexes;
  49.     vertexes.emplace_back(0, -1, x1, y1, 0, 1);
  50.     vertexes.emplace_back(1, -1, x1, y1, 1, 1);
  51.     vertexes.emplace_back(2, -1, x1, y1, 2, 1);
  52.     vertexes.emplace_back(3, -1, x1, y1, 3, 1);
  53.     vertexes.emplace_back(4, -1, x1, y1, 0, -1);
  54.     vertexes.emplace_back(5, -1, x1, y1, 1, -1);
  55.     vertexes.emplace_back(6, -1, x1, y1, 2, -1);
  56.     vertexes.emplace_back(7, -1, x1, y1, 3, -1);
  57.     visited[x1][y1][0][0] = 1;
  58.     visited[x1][y1][1][0] = 1;
  59.     visited[x1][y1][2][0] = 1;
  60.     visited[x1][y1][3][0] = 1;
  61.     visited[x1][y1][0][1] = 1;
  62.     visited[x1][y1][1][1] = 1;
  63.     visited[x1][y1][2][1] = 1;
  64.     visited[x1][y1][3][1] = 1;
  65.  
  66.     int sz = 8;
  67.  
  68.     queue<vertex> q;
  69.     q.push({0, -1, x1, y1, 0, 1});
  70.     q.push({1, -1, x1, y1, 1, 1});
  71.     q.push({2, -1, x1, y1, 2, 1});
  72.     q.push({3, -1, x1, y1, 3, 1});
  73.     q.push({4, -1, x1, y1, 0, -1});
  74.     q.push({5, -1, x1, y1, 1, -1});
  75.     q.push({6, -1, x1, y1, 2, -1});
  76.     q.push({7, -1, x1, y1, 3, -1});
  77.     vertex top_vertex;
  78.  
  79.     while(!q.empty()) {
  80.         top_vertex = q.front();
  81.         //cout << top_vertex.x << " " << top_vertex.y << " " << top_vertex.direction << endl;
  82.         q.pop();
  83.         if (top_vertex.x == 5 && top_vertex.y == 5) {
  84.             int x;
  85.             x++;
  86.         }
  87.  
  88.         if (top_vertex.x == x2 && top_vertex.y == y2) {
  89.             break;
  90.         }
  91.         vertex tmp;
  92.         if (!top_vertex.super) {
  93.             if (top_vertex.lastTurn == -1) {
  94.                 if (!visited[top_vertex.x][top_vertex.y][(top_vertex.direction + 1) % 4][1]) {
  95.                     tmp = {sz++, top_vertex.number, top_vertex.x, top_vertex.y,
  96.                            (top_vertex.direction + 1) % 4,
  97.                            1, true};
  98.                     vertexes.emplace_back(tmp);
  99.                     q.push(vertexes[sz - 1]);
  100.                 }
  101.             }
  102.  
  103.             if (top_vertex.lastTurn == 1) {
  104.                 if (!visited[top_vertex.x][top_vertex.y][(top_vertex.direction + 3) % 4][0]) {
  105.                     tmp = {sz++, top_vertex.number, top_vertex.x, top_vertex.y,
  106.                            (top_vertex.direction + 3) % 4,
  107.                            -1, true};
  108.                     vertexes.emplace_back(tmp);
  109.                     q.push(vertexes[sz - 1]);
  110.                 }
  111.             }
  112.             if (!visited[top_vertex.x][top_vertex.y][(top_vertex.direction + 2) % 4][(top_vertex.lastTurn + 1) / 2]) {
  113.                 tmp = {sz++, top_vertex.number, top_vertex.x, top_vertex.y,
  114.                        (top_vertex.direction + 2) % 4,
  115.                        top_vertex.lastTurn, true};
  116.                 vertexes.emplace_back(tmp);
  117.                 q.push(vertexes[sz - 1]);
  118.             }
  119.         }
  120.  
  121.         if (top_vertex.direction == 0) {
  122.             if (field[top_vertex.x - 1][top_vertex.y] > 0) {
  123.                 if (!visited[top_vertex.x - 1][top_vertex.y][top_vertex.direction][(top_vertex.lastTurn + 1) / 2]) {
  124.                     tmp = {sz++, top_vertex.number, top_vertex.x - 1, top_vertex.y,
  125.                            top_vertex.direction,
  126.                            top_vertex.lastTurn};
  127.                     vertexes.emplace_back(tmp);
  128.                     q.push(vertexes[sz - 1]);
  129.                     visited[top_vertex.x - 1][top_vertex.y][top_vertex.direction][(top_vertex.lastTurn + 1) / 2] = 1;
  130.                 }
  131.             }
  132.         }
  133.  
  134.         if (top_vertex.direction == 1) {
  135.             if (field[top_vertex.x][top_vertex.y + 1] > 0) {
  136.                 if (!visited[top_vertex.x][top_vertex.y + 1][top_vertex.direction][(top_vertex.lastTurn + 1) / 2]) {
  137.                     tmp = {sz++, top_vertex.number, top_vertex.x, top_vertex.y + 1,
  138.                            top_vertex.direction,
  139.                            top_vertex.lastTurn};
  140.                     vertexes.emplace_back(tmp);
  141.                     q.push(vertexes[sz - 1]);
  142.                     visited[top_vertex.x][top_vertex.y + 1][top_vertex.direction][(top_vertex.lastTurn + 1) / 2] = 1;
  143.                 }
  144.             }
  145.         }
  146.         if (top_vertex.direction == 2) {
  147.             if (field[top_vertex.x + 1][top_vertex.y] > 0) {
  148.                 if (!visited[top_vertex.x + 1][top_vertex.y][top_vertex.direction][(top_vertex.lastTurn + 1) / 2]) {
  149.                     tmp = {sz++, top_vertex.number, top_vertex.x + 1, top_vertex.y,
  150.                            top_vertex.direction,
  151.                            top_vertex.lastTurn};
  152.                     vertexes.emplace_back(tmp);
  153.                     q.push(vertexes[sz - 1]);
  154.                     visited[top_vertex.x + 1][top_vertex.y][top_vertex.direction][(top_vertex.lastTurn + 1) / 2] = 1;
  155.                 }
  156.             }
  157.         }
  158.         if (top_vertex.direction == 3) {
  159.             if (field[top_vertex.x][top_vertex.y - 1] > 0) {
  160.                 if (!visited[top_vertex.x][top_vertex.y - 1][top_vertex.direction][(top_vertex.lastTurn + 1) / 2]) {
  161.                     tmp = {sz++, top_vertex.number, top_vertex.x, top_vertex.y - 1,
  162.                            top_vertex.direction,
  163.                            top_vertex.lastTurn};
  164.                     vertexes.emplace_back(tmp);
  165.                     q.push(vertexes[sz - 1]);
  166.                     visited[top_vertex.x][top_vertex.y - 1][top_vertex.direction][(top_vertex.lastTurn + 1) / 2] = 1;
  167.                 }
  168.             }
  169.         }
  170.     }
  171.  
  172.     vector<pair<int,int>> ansf, anss;
  173.     if (top_vertex.x == x2 && top_vertex.y == y2) {
  174.         do {
  175.             ansf.emplace_back(top_vertex.x, top_vertex.y);
  176.             if (top_vertex.parent != -1)
  177.                 top_vertex = vertexes[top_vertex.parent];
  178.         } while (top_vertex.parent != -1);
  179.  
  180.         anss.push_back(ansf[ansf.size() - 1]);
  181.         for (int i = ansf.size() - 2; i >= 0; i--) {
  182.             if (ansf[i] != ansf[i + 1]) {
  183.                 anss.push_back(ansf[i]);
  184.             }
  185.         }
  186.         cout << anss.size() << endl;
  187.         cout << x1 << " " << x2 << endl;
  188.         for (auto el : anss) {
  189.             cout << el.first << " " << el.second << endl;
  190.         }
  191.     }
  192.     else cout << -1;
  193.    return 0;
  194. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement