Guest User

Untitled

a guest
Oct 17th, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.57 KB | None | 0 0
  1. //구슬 탈출 2
  2. #include <cstdio>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6. struct xy {
  7. int y;
  8. int x;
  9. void set(int yy, int xx) {
  10. y = yy;
  11. x = xx;
  12. }
  13. friend bool operator==(xy a, xy b) {
  14. return (a.x == b.x) && (a.y == b.y);
  15. }
  16. };
  17. int X, Y;
  18. char c;
  19. vector<vector<int>> map;
  20. xy r, b, hole;
  21. queue<pair<xy, xy>> q;
  22. queue<int> cnt;
  23. bool left() {
  24. int cr = r.x, cb = b.x;
  25. while (cr > 0) {
  26. if (map[r.y][cr - 1] != 1 && map[r.y][cr - 1] != 5)
  27. cr--;
  28. else if (map[r.y][cr - 1] == 5) {
  29. cr--;
  30. break;
  31. }
  32. else
  33. break;
  34. }
  35. while (cb > 0) {
  36. if (map[b.y][cb - 1] != 1 && map[b.y][cb - 1] != 5)
  37. cb--;
  38. else if (map[b.y][cb - 1] == 5) {
  39. cb--;
  40. break;
  41. }
  42. else
  43. break;
  44. }
  45. if (r.y == b.y && cr == cb && map[r.y][cr] != 5) {
  46. if (r.x < b.x)
  47. cb++;
  48. else
  49. cr++;
  50. }
  51. if (r.x == cr && b.x == cb)
  52. return false;
  53. r.x = cr; b.x = cb;
  54. return true;
  55. }
  56. bool right() {
  57. int cr = r.x, cb = b.x;
  58. while (cr < X - 1) {
  59. if (map[r.y][cr + 1] != 1 && map[r.y][cr + 1] != 5)
  60. cr++;
  61. else if (map[r.y][cr + 1] == 5) {
  62. cr++;
  63. break;
  64. }
  65. else
  66. break;
  67. }
  68. while (cb < X - 1) {
  69. if (map[b.y][cb + 1] != 1 && map[b.y][cb + 1] != 5)
  70. cb++;
  71. else if (map[b.y][cb + 1] == 5) {
  72. cb++;
  73. break;
  74. }
  75. else
  76. break;
  77. }
  78. if (r.y == b.y && cr == cb && map[r.y][cr] != 5) {
  79. if (r.x > b.x)
  80. cb--;
  81. else
  82. cr--;
  83. }
  84. if (r.x == cr && b.x == cb)
  85. return false;
  86. r.x = cr; b.x = cb;
  87. return true;
  88. }
  89. bool down() {
  90. int cr = r.y, cb = b.y;
  91. while (cr < Y - 1) {
  92. if (map[cr + 1][r.x] != 1 && map[cr + 1][r.x] != 5)
  93. cr++;
  94. else if (map[cr + 1][r.x] == 5) {
  95. cr++;
  96. break;
  97. }
  98. else
  99. break;
  100. }
  101. while (cb < Y - 1) {
  102. if (map[cb + 1][b.x] != 1 && map[cb + 1][b.x] != 5)
  103. cb++;
  104. else if (map[cb + 1][b.x] == 5) {
  105. cb++;
  106. break;
  107. }
  108. else
  109. break;
  110. }
  111. if (r.x == b.x && cr == cb && map[cb][b.x] != 5) {
  112. if (r.y > b.y)
  113. cb--;
  114. else
  115. cr--;
  116. }
  117. if (r.y == cr && b.y == cb)
  118. return false;
  119. r.y = cr; b.y = cb;
  120. return true;
  121. }
  122. bool up() {
  123. int cr = r.y, cb = b.y;
  124. while (cr > 0) {
  125. if (map[cr - 1][r.x] != 1 && map[cr - 1][r.x] != 5)
  126. cr--;
  127. else if (map[cr - 1][r.x] == 5) {
  128. cr--;
  129. break;
  130. }
  131. else
  132. break;
  133. }
  134. while (cb > 0) {
  135. if (map[cb - 1][b.x] != 1 && map[cb - 1][b.x] != 5)
  136. cb--;
  137. else if (map[cb - 1][b.x] == 5) {
  138. cb--;
  139. break;
  140. }
  141. else
  142. break;
  143. }
  144. if (r.x == b.x && cr == cb && map[cb][b.x] != 5) {
  145. if (r.y < b.y)
  146. cb++;
  147. else
  148. cr++;
  149. }
  150. if (r.y == cr && b.y == cb)
  151. return false;
  152. r.y = cr; b.y = cb;
  153. return true;
  154. }
  155. bool move(int n) {
  156. if (n == 0)
  157. return right();
  158. else if (n == 1)
  159. return down();
  160. else if (n == 2)
  161. return left();
  162. else
  163. return up();
  164. }
  165. int main() {
  166. scanf("%d%d", &Y, &X);
  167. for (int i = 0; i < Y; i++) {
  168. vector<int> tmp(X);
  169. map.push_back(tmp);
  170. for (int j = 0; j < X; j++) {
  171. scanf(" %c", &c);
  172. if (c == '#')
  173. map[i][j] = 1;
  174. else if (c == 'R')
  175. r.set(i, j);
  176. else if (c == 'B')
  177. b.set(i, j);
  178. else if (c == 'O') {
  179. map[i][j] = 5;
  180. hole.set(i, j);
  181. }
  182. }
  183. }
  184. int ans = 11, curcnt = 0, find = 0;
  185. q.push(make_pair(r, b));
  186. cnt.push(0);
  187. pair<xy, xy> cur;
  188. while (!q.empty() && curcnt < 10) {
  189. curcnt = cnt.front(); cnt.pop();
  190. cur = q.front(); q.pop();
  191. for (int i = 0; i < 4; i++) {
  192. r = cur.first; b = cur.second;
  193. if (!move(i)) {
  194. map[r.y][r.x] = 0;
  195. map[b.y][b.x] = 0;
  196. continue;
  197. }
  198. if (b == hole)
  199. ;
  200. else if (r == hole) {
  201. ans = curcnt + 1;
  202. find = 1;
  203. }
  204. else {
  205. cnt.push(curcnt + 1);
  206. q.push(make_pair(r, b));
  207. }
  208. if (find == 1)
  209. break;
  210. }
  211. if (find == 1)
  212. break;
  213. }
  214. if (ans == 11)
  215. ans = -1;
  216. printf("%d\n", ans);
  217. return 0;
  218. }
Add Comment
Please, Sign In to add comment