fork download 
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4. using namespace std;
  5.  
  6.  
  7. int arr[100][100]; // 0: 빈 공간, 1: 미네랄
  8. int bfs_arr[100][100]; // 0: 빈 공간, 1: 확인 X, 2: 바닥에 붙어 있는 미네랄, 3: 공중에 떠 있는 미네랄 
  9.  
  10.  
  11. void bfs(int R, int C, int y, int x, int value) {
  12. 	int dy[4] = { 0,0,1,-1 };
  13. 	int dx[4] = { 1,-1,0,0 };
  14.  
  15. 	queue<pair<int, int>> q;
  16. 	q.push(make_pair(y, x));
  17. 	bfs_arr[y][x] = value;
  18.  
  19. 	while (!q.empty()) {
  20. 		int y = q.front().first;
  21. 		int x = q.front().second;
  22. 		q.pop();
  23.  
  24. 		for (int i = 0; i < 4; i++) {
  25. 			int ny = y + dy[i];
  26. 			int nx = x + dx[i];
  27. 			if (0 <= ny && ny < R && 0 <= nx && nx < C) {
  28. 				if (bfs_arr[ny][nx] == 1) {
  29. 					q.push(make_pair(ny, nx));
  30. 					bfs_arr[ny][nx] = value;
  31. 				}
  32. 			}
  33. 		}
  34. 	}
  35. }
  36.  
  37. /**
  38. * return 0: 섬 1개, 1: 섬 2개 이상
  39. */
  40. int world_bfs(int R, int C) {
  41. 	int island = 0;
  42.  
  43. 	for (int i = 0; i < R; i++) {
  44. 		for (int j = 0; j < C; j++) {
  45. 			bfs_arr[i][j] = arr[i][j];
  46. 		}
  47. 	}
  48.  
  49. 	for (int i = 0; i < C; i++) {
  50. 		if (R - 1 >= 0 && bfs_arr[R - 1][i] == 1) {
  51. 			bfs(R, C, R - 1, i, 2);
  52. 		}
  53. 	}
  54. 	// 바닥에 붙은 미네랄 처리
  55.  
  56. 	for (int i = 0; i < R; i++) {
  57. 		for (int j = 0; j < C; j++) {
  58. 			if (bfs_arr[i][j] == 1) {
  59. 				bfs(R, C, i, j, 3);
  60. 				island = 1;
  61. 			}
  62. 		}
  63. 	}
  64. 	// 공중에 떠 있는 미네랄 처리
  65.  
  66. 	return island;
  67. }
  68.  
  69. /**
  70. * return 0: 내리기 실패, 1: 내리기 성공
  71. */
  72. int drop(int R, int C) {
  73. 	int check_arr[100][100];
  74. 	int check = 1;
  75.  
  76. 	for (int i = 0; i < R; i++) {
  77. 		for (int j = 0; j < C; j++) {
  78. 			check_arr[i][j] = bfs_arr[i][j];
  79. 		}
  80. 	}
  81.  
  82. 	for (int i = 0; i < C; i++) {
  83. 		if (check_arr[R - 1][i] == 3) {
  84. 			check = 0;
  85. 			return check;
  86. 		}
  87. 		// case 1: 바닥에 닿는 경우
  88. 	}
  89. 	for (int i = R - 2; i >= 0; i--) {
  90. 		for (int j = 0; j < C; j++) {
  91.  
  92. 			if (check_arr[i][j] == 3 && check_arr[i + 1][j] == 2) {
  93. 				check = 0;
  94. 				return check;
  95. 			}
  96. 			// case 2: 클러스터에 닿는 경우
  97. 			else if (check_arr[i][j] == 3 && check_arr[i + 1][j] == 0) {
  98. 				check_arr[i + 1][j] = check_arr[i][j];
  99. 				check_arr[i][j] = 0;
  100. 			}
  101. 			// case 3: 내려도 되는 경우
  102.  
  103. 		}
  104. 	}
  105.  
  106. 	for (int i = 0; i < R; i++) {
  107. 		for (int j = 0; j < C; j++) {
  108. 			bfs_arr[i][j] = check_arr[i][j];
  109. 		}
  110. 	}
  111. 	return check;
  112. }
  113.  
  114. void break_mineral(queue<int>& height, int R, int C, int N, int dir) {
  115. 	int h = R - height.front();
  116. 	height.pop();
  117.  
  118. 	if (dir == 0) {
  119. 		for (int i = 0; i < C; i++) {
  120. 			if (arr[h][i] == 1) {
  121. 				arr[h][i] = 0;
  122. 				break;
  123. 			}
  124. 		}
  125. 	}
  126. 	else {
  127. 		for (int i = C - 1; i >= 0; i--) {
  128. 			if (arr[h][i] == 1) {
  129. 				arr[h][i] = 0;
  130. 				break;
  131. 			}
  132. 		}
  133. 	}
  134. }
  135.  
  136. void sol(queue<int>& height, int R, int C, int N) {
  137. 	int dir = 0; // 0: 왼쪽 1: 오른쪽
  138. 	for (int i = 0; i < N; i++) {
  139. 		if (!height.empty()) {
  140. 			break_mineral(height, R, C, N, dir);
  141. 			dir = (dir + 1) % 2;
  142. 		}
  143. 		// 막대기 투척 코드
  144.  
  145. 		int island = world_bfs(R, C);
  146. 		// BFS 코드
  147.  
  148. 		if (island == 1) {
  149. 			while (drop(R, C) == 1) {}
  150. 		}
  151.  
  152. 		for (int i = 0; i < R; i++) {
  153. 			for (int j = 0; j < C; j++) {
  154. 				if (bfs_arr[i][j] != 0)
  155. 					arr[i][j] = 1;
  156. 				else
  157. 					arr[i][j] = 0;
  158. 			}
  159. 		}
  160. 		// arr 갱신 코드
  161. 	}
  162. }
  163.  
  164. int main() {
  165. 	int R, C;
  166. 	int N;
  167. 	queue<int> height;
  168.  
  169. 	cin >> R >> C;
  170. 	for (int i = 0; i < R; i++) {
  171. 		for (int j = 0; j < C; j++) {
  172. 			char input;
  173. 			cin >> input;
  174. 			if (input == '.') {
  175. 				arr[i][j] = 0;
  176. 			}
  177. 			else {
  178. 				arr[i][j] = 1;
  179. 			}
  180. 		}
  181. 	}
  182.  
  183. 	cin >> N;
  184. 	for (int i = 0; i < N; i++) {
  185. 		int input;
  186. 		cin >> input;
  187. 		height.push(input);
  188. 	}
  189.  
  190. 	sol(height, R, C, N);
  191.  
  192. 	for (int i = 0; i < R; i++) {
  193. 		for (int j = 0; j < C; j++) {
  194. 			if (arr[i][j] == 0)
  195. 				cout << '.';
  196. 			else
  197. 				cout << 'X';
  198. 		}
  199. 		if (i != R - 1) cout << endl;
  200. 	}
  201.  
  202. 	return 0;
  203. }
Success #stdin #stdout 0.01s 5600KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/KXITq7
language:
C++ (gcc 8.3)
created:
4 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!