Advertisement
Guest User

Untitled

a guest
May 25th, 2016
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 14.25 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <string>
  7. #include <set>
  8.  
  9. using namespace std;
  10.  
  11. typedef long long ll;
  12.  
  13. const ll INF = 1e9;
  14.  
  15. #define pos pair<ll, ll>
  16. #define x first
  17. #define y second
  18. #define mp make_pair
  19.  
  20. int main() {
  21. ll n, m;
  22. cin >> n >> m;
  23. vector<string> g(n);
  24. for (int i = 0; i < n; ++i) {
  25. cin >> g[i];
  26. }
  27.  
  28. pos b; // стартовая вершина
  29. cin >> b.x >> b.y;
  30. b.x--, b.y--;
  31. pos e;
  32. cin >> e.x >> e.y;
  33. e.x--, e.y--;
  34. vector<vector<pos>> d(n, vector<pos>(m, pos(INF, 0)));
  35. d[b.x][b.y] = pos(0, 0);
  36. vector<vector<char>> u(n);
  37. set<pair<pos, pos>> q;
  38. q.insert(make_pair(d[b.x][b.y], b));
  39. while (!q.empty()) {
  40. pos v = q.begin()->second;
  41. q.erase(q.begin());
  42. if (g[v.x][v.y] == '+') {
  43. if (v.x > 0 && d[v.x][v.y].x + 1 < d[v.x - 1][v.y].x) {
  44. q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  45. d[v.x - 1][v.y].x = d[v.x][v.y].x + 1;
  46. q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  47. }
  48. if (v.y > 0 && d[v.x][v.y].y + 1 < d[v.x][v.y - 1].x) {
  49. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  50. d[v.x][v.y - 1].x = d[v.x][v.y].x + 1;
  51. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  52. }
  53. if (v.x < n - 1 && d[v.x][v.y].x + 1 < d[v.x + 1][v.y].x) {
  54. q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  55. d[v.x + 1][v.y].x = d[v.x][v.y].x + 1;
  56. q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  57. }
  58. if (v.y < m - 1 && d[v.x][v.y].y + 1 < d[v.x][v.y + 1].x) {
  59. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  60. d[v.x][v.y - 1].x = d[v.x][v.y].x + 1;
  61. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  62. }
  63. }
  64. //« - » означает, что этот блок имеет 2 двери — в соседний слева и соседний справа блок;
  65. if (g[v.x][v.y] == '-') {
  66. if (v.x > 0 && d[v.x][v.y].x + d[v.x][v.y].y % 2 < d[v.x - 1][v.y].x) {
  67. q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  68. d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  69. q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  70. }
  71. if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 2 < d[v.x][v.y - 1].x) {
  72. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  73. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  74. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  75. }
  76. if (v.x < n - 1 && d[v.x][v.y].x + d[v.x][v.y].y % 2 < d[v.x + 1][v.y].x) {
  77. q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  78. d[v.x + 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  79. q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  80. }
  81. if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 2 < d[v.x][v.y + 1].x) {
  82. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  83. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  84. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  85. }
  86. }
  87. //« | » означает, что этот блок имеет 2 двери — в соседний сверху и снизу блоки;
  88. if (g[v.x][v.y] == '|') {
  89. if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2 < d[v.x - 1][v.y].x) {
  90. q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  91. d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  92. q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  93. }
  94. if (v.y > 0 && d[v.x][v.y].y + d[v.x][v.y].y % 2 < d[v.x][v.y - 1].x) {
  95. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  96. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  97. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  98. }
  99. if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2 < d[v.x + 1][v.y].x) {
  100. q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  101. d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
  102. q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  103. }
  104. if (v.y < m - 1 && d[v.x][v.y].y + d[v.x][v.y].y % 2 < d[v.x][v.y + 1].x) {
  105. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  106. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  107. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  108. }
  109. }
  110. //«^» означает, что этот блок имеет 1 дверь — в соседний сверху блок;
  111. if (g[v.x][v.y] == '^') {
  112. if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 3) % 4 < d[v.x - 1][v.y].x) {
  113. q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  114. d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  115. q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  116. }
  117. if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y) % 4 < d[v.x][v.y - 1].x) {
  118. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  119. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  120. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  121. }
  122. if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 4 < d[v.x + 1][v.y].x) {
  123. q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  124. d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
  125. q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  126. }
  127. if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 2) % 4 < d[v.x][v.y + 1].x) {
  128. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  129. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  130. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  131. }
  132. }
  133. //«>» означает, что этот блок имеет 1 дверь — в соседний справа блок;
  134. if (g[v.x][v.y] == '>') {
  135. if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 2) % 4 < d[v.x - 1][v.y].x) {
  136. q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  137. d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  138. q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  139. }
  140. if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 3) % 4 < d[v.x][v.y - 1].x) {
  141. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  142. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  143. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  144. }
  145. if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 0) % 4 < d[v.x + 1][v.y].x) {
  146. q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  147. d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
  148. q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  149. }
  150. if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 4 < d[v.x][v.y + 1].x) {
  151. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  152. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  153. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  154. }
  155. }
  156. //«v» означает, что этот блок имеет 1 дверь — в соседний снизу блок;
  157. if (g[v.x][v.y] == 'v') {
  158. if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 4 < d[v.x - 1][v.y].x) {
  159. q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  160. d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  161. q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  162. }
  163. if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 2) % 4 < d[v.x][v.y - 1].x) {
  164. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  165. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  166. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  167. }
  168. if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 3) % 4 < d[v.x + 1][v.y].x) {
  169. q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  170. d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
  171. q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  172. }
  173. if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 0) % 4 < d[v.x][v.y + 1].x) {
  174. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  175. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  176. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  177. }
  178. }
  179. //«<» означает, что этот блок имеет 1 дверь — в соседний слева блок;
  180. if (g[v.x][v.y] == '<') {
  181. if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 0) % 4 < d[v.x - 1][v.y].x) {
  182. q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  183. d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  184. q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  185. }
  186. if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 4 < d[v.x][v.y - 1].x) {
  187. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  188. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  189. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  190. }
  191. if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 2) % 4 < d[v.x + 1][v.y].x) {
  192. q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  193. d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
  194. q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  195. }
  196. if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 3) % 4 < d[v.x][v.y + 1].x) {
  197. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  198. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  199. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  200. }
  201. }
  202. //«L» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний слева блок;
  203. if (g[v.x][v.y] == 'L') {
  204. if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 0) % 4 == 0 < d[v.x - 1][v.y].x) {
  205. q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  206. d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  207. q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  208. }
  209. if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 4 == 0 < d[v.x][v.y - 1].x) {
  210. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  211. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  212. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  213. }
  214. if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 2) % 4 == 0 < d[v.x + 1][v.y].x) {
  215. q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  216. d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
  217. q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  218. }
  219. if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 3) % 4 == 0 < d[v.x][v.y + 1].x) {
  220. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  221. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  222. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  223. }
  224. }
  225. //«R» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний справа блок;
  226. if (g[v.x][v.y] == 'R') {
  227. if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 2) % 4 == 0 < d[v.x - 1][v.y].x) {
  228. q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  229. d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  230. q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  231. }
  232. if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 3) % 4 == 0 < d[v.x][v.y - 1].x) {
  233. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  234. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  235. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  236. }
  237. if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 0) % 4 < d[v.x + 1][v.y].x) {
  238. q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  239. d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
  240. q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  241. }
  242. if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 4 < d[v.x][v.y + 1].x) {
  243. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  244. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  245. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  246. }
  247. }
  248. //«U» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний сверху блок;
  249. if (g[v.x][v.y] == 'U') {
  250. if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 2) % 4 == 0 < d[v.x - 1][v.y].x) {
  251. q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  252. d[v.x - 1][v.y].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  253. q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  254. }
  255. if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 3) % 4 == 0 < d[v.x][v.y - 1].x) {
  256. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  257. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  258. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  259. }
  260. if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 0) % 4 == 0 < d[v.x + 1][v.y].x) {
  261. q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  262. d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
  263. q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  264. }
  265. if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 1) % 4 == 0 < d[v.x][v.y + 1].x) {
  266. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  267. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  268. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  269. }
  270. }
  271. //«D» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний снизу блок;
  272. if (g[v.x][v.y] == 'D') {
  273. if (v.x > 0 && d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 4 == 0 < d[v.x - 1][v.y].x) {
  274. q.erase(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  275. d[v.x - 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 4 == 0;
  276. q.insert(make_pair(d[v.x - 1][v.y], pos(v.x - 1, v.y)));
  277. }
  278. if (v.y > 0 && d[v.x][v.y].y + (d[v.x][v.y].y + 2) % 4 == 0 < d[v.x][v.y - 1].x) {
  279. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  280. d[v.x][v.y - 1].x = d[v.x][v.y].x + (d[v.x][v.y].y + 2) % 4 == 0;
  281. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  282. }
  283. if (v.x < n - 1 && d[v.x][v.y].x + (d[v.x][v.y].y + 3) % 4 == 0 < d[v.x + 1][v.y].x) {
  284. q.erase(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  285. d[v.x + 1][v.y].x = d[v.x][v.y].x + (d[v.x][v.y].y + 1) % 2;
  286. q.insert(make_pair(d[v.x + 1][v.y], pos(v.x + 1, v.y)));
  287. }
  288. if (v.y < m - 1 && d[v.x][v.y].y + (d[v.x][v.y].y + 0) % 4 == 0 < d[v.x][v.y + 1].x) {
  289. q.erase(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  290. d[v.x][v.y - 1].x = d[v.x][v.y].x + d[v.x][v.y].y % 2;
  291. q.insert(make_pair(d[v.x][v.y - 1], pos(v.x, v.y - 1)));
  292. }
  293. }
  294. }
  295. return 0;
  296. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement