fork download
copy 
  1. #include<stdio.h>
  2.  
  3. #pragma warning(disable:4996)
  4.  
  5. int que[11000][5];
  6.  
  7. int N, M;
  8.  
  9. int map[12][12];//체크는 빨간색과 파란색이 같은 곳에 있는지 확인해야함 그래서 빨강색이 체크chk[x][y]일때 파란색의 좌표가 [0][1];
  10.  
  11. int st = -1, ed = -1, chk = 0, ans = 0;
  12.  
  13. int chk_cnt[10000];
  14.  
  15. int blue[2], red[2];
  16.  
  17. int xm[4] = { 1,0,-1,0 }, ym[4] = { 0,1,0,-1 };
  18.  
  19. int main() {
  20.  
  21. 	char hold;
  22.  
  23. 	scanf("%d%d", &N, &M);
  24.  
  25. 	for (int i = 0; i < N; i++) {
  26.  
  27. 		for (int j = 0; j < M; j++) {
  28.  
  29. 			scanf(" %c", &hold);
  30.  
  31. 			if (hold == '.')map[i][j] = 0;
  32.  
  33. 			else if (hold == '#')map[i][j] = 1;
  34.  
  35. 			else if (hold == 'B') {
  36.  
  37. 				map[i][j] = 2;
  38.  
  39. 				blue[0] = i;
  40.  
  41. 				blue[1] = j;
  42.  
  43. 			}
  44.  
  45. 			else if (hold == 'R') {
  46.  
  47. 				map[i][j] = 3;
  48.  
  49. 				red[0] = i;
  50.  
  51. 				red[1] = j;
  52.  
  53. 			}
  54.  
  55. 			else if (hold == 'O')map[i][j] = 4;
  56.  
  57. 		}
  58.  
  59. 	}
  60.  
  61. 	que[++st][0] = red[0];
  62.  
  63. 	que[st][1] = red[1];
  64.  
  65. 	que[st][2] = blue[0];
  66.  
  67. 	que[st][3] = blue[1];
  68.  
  69. 	chk_cnt[(red[0] - 1) + (red[1] - 1) * 10 + (blue[0] - 1) * 100 + (blue[1] - 1) * 1000] = 1;
  70.  
  71. 	while (ans == 0 && st > ed) {
  72.  
  73. 		red[0] = que[++ed][0];
  74.  
  75. 		red[1] = que[ed][1];
  76.  
  77. 		blue[0] = que[ed][2];
  78.  
  79. 		blue[1] = que[ed][3];
  80.  
  81. 		if (que[ed][4] >= 11)break;
  82.  
  83. 		map[red[0]][red[1]] = 3;
  84.  
  85. 		map[blue[0]][blue[1]] = 2;
  86.  
  87. 		for (int i = 0; i < 4; i++) {
  88.  
  89. 			if (map[red[0] + ym[i]][red[1] + xm[i]] == 0) {//암것도 없으면 간다
  90.  
  91. 				chk = 1;
  92.  
  93. 				map[red[0]][red[1]] = 0;
  94.  
  95. 				while (map[red[0] + ym[i]][red[1] + xm[i]] == 0) {
  96.  
  97. 					red[0] += ym[i];
  98.  
  99. 					red[1] += xm[i];
  100.  
  101. 				}
  102.  
  103. 				map[red[0]][red[1]] = 3;
  104.  
  105. 			}
  106.  
  107. 			if (map[red[0] + ym[i]][red[1] + xm[i]] == 4) {//골인지점이면 간다
  108.  
  109. 				ans = 1;//빨간공이 일단 들어가긴 했음
  110.  
  111. 				map[red[0]][red[1]] = 0;
  112.  
  113. 			}
  114.  
  115. 			if (map[blue[0] + ym[i]][blue[1] + xm[i]] == 0) {
  116.  
  117. 				chk = 1;
  118.  
  119. 				map[blue[0]][blue[1]] = 0;
  120.  
  121. 				while (map[blue[0] + ym[i]][blue[1] + xm[i]] == 0) {
  122.  
  123. 					blue[0] += ym[i];
  124.  
  125. 					blue[1] += xm[i];
  126.  
  127. 				}
  128.  
  129. 				map[blue[0]][blue[1]] = 2;
  130.  
  131. 			}
  132.  
  133. 			if (map[blue[0] + ym[i]][blue[1] + xm[i]] == 4) {//파란공이 들어감
  134.  
  135. 				chk = 3;
  136.  
  137. 				ans = 0;
  138.  
  139. 			}
  140.  
  141. 			if (map[red[0] + ym[i]][red[1] + xm[i]] == 0) {//암것도 없으며 간다
  142.  
  143. 				map[red[0]][red[1]] = 0;
  144.  
  145. 				while (map[red[0] + ym[i]][red[1] + xm[i]] == 0) {//파란공에 막혔었는 문제 해결
  146.  
  147. 					red[0] += ym[i];
  148.  
  149. 					red[1] += xm[i];
  150.  
  151. 				}
  152.  
  153. 				map[red[0]][red[1]] = 3;
  154.  
  155. 			}
  156.  
  157. 			if (ans == 1) {
  158.  
  159. 				que[ed][4]++;
  160.  
  161. 				break;
  162.  
  163. 			}
  164.  
  165. 			if (chk == 1 && chk_cnt[(red[0] - 1) + (red[1] - 1) * 10 + (blue[0] - 1) * 100 + (blue[1] - 1) * 1000] == 0) {//움직였고, 그 포지션에 위치한적이 없으면
  166.  
  167. 				chk_cnt[(red[0] - 1) + (red[1] - 1) * 10 + (blue[0] - 1) * 100 + (blue[1] - 1) * 1000] = 1;
  168.  
  169. 				que[++st][0] = red[0];
  170.  
  171. 				que[st][1] = red[1];
  172.  
  173. 				que[st][2] = blue[0];
  174.  
  175. 				que[st][3] = blue[1];
  176.  
  177. 				que[st][4] = que[ed][4] + 1;
  178.  
  179. 			}
  180.  
  181. 			chk = 0;
  182.  
  183. 			map[red[0]][red[1]] = 0;
  184.  
  185. 			map[blue[0]][blue[1]] = 0;//현위치 초기화
  186.  
  187. 			map[que[ed][0]][que[ed][1]] = 3;
  188.  
  189. 			map[que[ed][2]][que[ed][3]] = 2;//다시 원래의 자리로 마킹
  190.  
  191. 			red[0] = que[ed][0];
  192.  
  193. 			red[1] = que[ed][1];
  194.  
  195. 			blue[0] = que[ed][2];
  196.  
  197. 			blue[1] = que[ed][3];//원래자리로 공 보내기
  198.  
  199. 		}
  200.  
  201. 		map[que[ed][0]][que[ed][1]] = 0;//맵에서 공을 지움
  202.  
  203. 		map[que[ed][2]][que[ed][3]] = 0;
  204.  
  205. 	}
  206.  
  207. 	if (ans == 1)printf("%d", que[ed][4]);
  208.  
  209. 	else printf("-1");
  210.  
  211. }
Success #stdin #stdout 0s 4244KB
comments (?)
stdin
copy 
10 10
##########
#.BR.....#
#.#####..#
#.#...#..#
#.#.#..O.#
#.#.#....#
#.#....#.#
#.#..#...#
#.#......#
##########
stdout
copy 
11
https://ideone.com/tafSOQ
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!