Advertisement
Guest User

Untitled

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