Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.93 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. #include <utility>
  6.  
  7. enum {
  8. DOWN,
  9. LEFT,
  10. UP,
  11. RIGHT,
  12. };
  13.  
  14. struct Turns {
  15. int xx;
  16. int yy;
  17. int prev;
  18. };
  19.  
  20. struct Cond {
  21. int xx;
  22. int yy;
  23. int dir;
  24. int rot;
  25.  
  26. Cond(int x_p, int y_p, int d_p, int r_p)
  27. : xx(x_p), yy(y_p), dir(d_p), rot(r_p) {
  28. }
  29. };
  30.  
  31. int GetDirection(int xx, int yy) {
  32. if (xx == -1)
  33. return UP;
  34. if (xx == 1)
  35. return DOWN;
  36. if (yy == 1)
  37. return RIGHT;
  38. if (yy == -1)
  39. return LEFT;
  40. return 0;
  41. }
  42.  
  43. int GetNumber(Cond cur)
  44. {
  45. if (cur.rot == LEFT){
  46. return cur.dir;
  47. }
  48. else {
  49. return cur.dir + 4;
  50. }
  51. }
  52.  
  53. void update(std::vector<std::vector<std::vector<std::pair<int, int>>>> &used, std::queue<Cond> &qq,
  54. std::vector<std::vector<std::vector<int>>> &dd,
  55. std::vector<std::vector<std::vector<Turns>>> &parent,
  56. Cond &cur, int x1x, int y1y) {
  57. int xxx = cur.xx;
  58. int yyy = cur.yy;
  59. Cond to_push(xxx + x1x, yyy + y1y, GetDirection(x1x, y1y), cur.rot);
  60.  
  61. if ((to_push.dir - cur.dir + 4) % 4 == 1) {
  62. to_push.rot = RIGHT;
  63. if (cur.rot == RIGHT)
  64. return;
  65. }
  66.  
  67. if ((to_push.dir - cur.dir + 4) % 4 == 3) {
  68. to_push.rot = LEFT;
  69. if (cur.rot == LEFT)
  70. return;
  71. }
  72.  
  73. if (used[xxx + x1x][yyy + y1y][to_push.dir].first == false &&
  74. (to_push.rot == LEFT || to_push.rot == 0)) {
  75. used[xxx + x1x][yyy + y1y][to_push.dir].first = true;
  76. dd[xxx + x1x][yyy + y1y][GetNumber(to_push)] =
  77. dd[xxx][yyy][GetNumber(cur)] + 1;
  78. qq.push(to_push);
  79. parent[xxx + x1x][yyy + y1y][GetNumber(to_push)] =
  80. {xxx, yyy, GetNumber(cur)};
  81. }
  82.  
  83. if (used[xxx + x1x][yyy + y1y][to_push.dir].second == false &&
  84. (to_push.rot == RIGHT || to_push.rot == 0)) {
  85. used[xxx + x1x][yyy + y1y][to_push.dir].second = true;
  86. dd[xxx + x1x][yyy + y1y][GetNumber(to_push)] =
  87. dd[xxx][yyy][GetNumber(cur)] + 1;
  88. qq.push(to_push);
  89. parent[xxx + x1x][yyy + y1y][GetNumber(to_push)] =
  90. {xxx, yyy, GetNumber(cur)};
  91. }
  92. }
  93.  
  94. std::vector<std::vector<std::vector<Turns>>>
  95. bfs(std::vector<std::vector<int>> &gg, std::pair<int, int> start, int *mi, int *num, std::pair<int, int> endd) {
  96. int nn = gg.size();
  97. int mm = gg[0].size();
  98. std::vector<std::vector<std::vector<std::pair<int, int>>>> used(nn,
  99. std::vector<std::vector<std::pair<int, int>>>(mm,
  100. std::vector<std::pair<int, int>>(
  101. 8, {0, 0})));
  102. std::vector<std::vector<std::vector<Turns>>> parent(nn,
  103. std::vector<std::vector<Turns>>(mm,
  104. std::vector<Turns>(8)));
  105. std::vector<std::vector<std::vector<int>>> dd(nn, std::vector<std::vector<int>>(mm,
  106. std::vector<int>(8, -1)));
  107. std::queue<Cond> qq;
  108.  
  109. for (int i = 0; i < 4; ++i) {
  110. used[start.first][start.second][i].first = true;
  111. used[start.first][start.second][i].second = true;
  112. }
  113.  
  114. qq.push(Cond(start.first, start.second, UP, 0));
  115. qq.push(Cond(start.first, start.second, DOWN, 0));
  116. qq.push(Cond(start.first, start.second, LEFT, 0));
  117. qq.push(Cond(start.first, start.second, RIGHT, 0));
  118.  
  119. while (!qq.empty()) {
  120. Cond cur = qq.front();
  121. qq.pop();
  122. int xxxx = cur.xx;
  123. int yyyy = cur.yy;
  124. if (xxxx + 1 < nn && gg[xxxx + 1][yyyy])
  125. update(used, qq, dd, parent, cur, 1, 0);
  126. if (xxxx > 0 && gg[xxxx - 1][yyyy])
  127. update(used, qq, dd, parent, cur, -1, 0);
  128. if (yyyy + 1 < mm && gg[xxxx][yyyy + 1])
  129. update(used, qq, dd, parent, cur, 0, 1);
  130. if (yyyy > 0 && gg[xxxx][yyyy - 1])
  131. update(used, qq, dd, parent, cur, 0, -1);
  132. }
  133.  
  134. for (int i = 0; i < 8; ++i) {
  135. if (dd[endd.first][endd.second][i] <= *mi && dd[endd.first][endd.second][i] != -1) {
  136. *mi = dd[endd.first][endd.second][i];
  137. *num = i;
  138. }
  139. }
  140. return parent;
  141. }
  142.  
  143.  
  144. int main() {
  145.  
  146. std::pair<int, int> start, endd;
  147. int n_n = 0, m_m = 0;
  148.  
  149. std::cin >> n_n >> m_m;
  150. std::vector<std::vector<int>> ggg(n_n, std::vector<int>(m_m));
  151. for (int i = 0; i < n_n; ++i) {
  152. for (int l = 0; l < m_m; ++l) {
  153. char input;
  154. std::cin >> input;
  155. if (input == '#')
  156. ggg[i][l] = 0;
  157. else
  158. ggg[i][l] = 1;
  159. }
  160. }
  161. std::cin >> start.first >> start.second;
  162. std::cin >> endd.first >> endd.second;
  163.  
  164. start.first--;
  165. start.second--;
  166. endd.first--;
  167. endd.second--;
  168. int res = 999999;
  169. int num = -1;
  170. std::vector<std::vector<std::vector<Turns>>> path = bfs(ggg, start, &res, &num, endd);
  171.  
  172. if (start.first == endd.first && start.second == endd.second) {
  173. std::cout << 0 << std::endl;
  174. std::cout << start.first + 1 << " " << start.second + 1 << std::endl;
  175. } else {
  176. if (num == -1) {
  177. std::cout << -1;
  178. } else {
  179. std::cout << res + 1 << std::endl;
  180. std::vector<std::pair<int, int>> result;
  181. result.push_back(endd);
  182. Turns current = path[endd.first][endd.second][num];
  183. for (int i = res + 1; i > 0; --i) {
  184. std::pair<int, int> tmp(current.xx, current.yy);
  185. result.push_back(tmp);
  186. current = path[current.xx][current.yy][current.prev];
  187. }
  188. reverse(result.begin(), result.end());
  189. for (int i = 0; i < res + 2; ++i) {
  190. std::cout << result[i].first + 1 << " " << result[i].second + 1 << std::endl;
  191. }
  192. }
  193. }
  194. return 0;
  195. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement