fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. #define MIN(a,b) a>b ? b:a;
  8. #define MAX(a,b) a<b ? b:a;
  9. const int oo = 0x3f3f3f3f;
  10.  
  11.  
  12. //문제 : NxN크기의 보드에서, 블록 상태가 주어졌을 때(상황)
  13. //		 최대 5번까지 이동시켜서 만들 수 있는 가장 큰 블록의 값을 구하시오.
  14. //동치 : 최대 5번까지 이동시킬 때, 나올 수 있는 모든 경우의 수를 구해서
  15. //		 그 중에 제일 큰 블록의 값을 find하기.
  16. //따라서 가능한 모든 경우를 구하되, 조건을 지켜가며 bfs하기. 흠? 이것도 결국 조건인데?
  17. //조건 : 상 하 좌 우로 밀때, 밀리는 곳부터 우선 처리되어야 하며, 한번만 밀려야 함.(즉, 한번 밀린건지, 아닌건지 판별 필요함)
  18. int N;
  19. //int backup_board[21][21];
  20.  
  21. int ans = -oo;
  22.  
  23. int find_max( int board[21][21]) 
  24. {
  25. 	int ret = -oo;
  26. 	for (int x = 1; x <= N; x++) 
  27. 	for (int y = 1; y <= N; y++) 
  28. 	{
  29. 		ret = MAX(ret, board[x][y]);
  30. 	}
  31.  
  32. 	return ret;
  33. }
  34.  
  35. //조건 해석하기
  36. void up( int board[21][21], int temp[21][21])
  37. {
  38. 	int canjoin[21][21] = { 0, };//yes가 0 no가 1
  39.  
  40. 	for (int y = 1; y <= N; y++) 
  41. 	{
  42. 		int t_idxx = 0;//들어온 원소 수라고 생각 최초는 empthy
  43. 		for (int x = 1; x <= N; x++) 
  44. 		{
  45. 			if (board[x][y] == 0) continue;
  46.  
  47. 			//board[x][y]에 뭔가 있을때..
  48. 			if (t_idxx == 0) {//처음껀 그냥 옮겨주고
  49. 				t_idxx++;
  50. 				temp[t_idxx][y] = board[x][y];
  51. 			}
  52. 			else {//나머지의 경우는 같은거 있는지 검사
  53. 				if (temp[t_idxx][y] == board[x][y] && canjoin[t_idxx][y] == 0) {
  54. 					temp[t_idxx][y] = temp[t_idxx][y] * 2;
  55. 					//t_idxx는 그대로 유지
  56. 					canjoin[t_idxx][y] = 1;
  57. 				}
  58. 				else {
  59. 					t_idxx++;
  60. 					temp[t_idxx][y] = board[x][y];
  61. 				}
  62. 			}
  63. 		}
  64. 		t_idxx++;
  65. 		while( t_idxx <= N)	temp[t_idxx++][y] = 0;
  66. 	}
  67. }
  68.  
  69. void down( int board[21][21], int temp[21][21])
  70. {
  71. 	int canjoin[21][21] = { 0, };//yes가 0 no가 1
  72.  
  73. 	for (int y = 1; y <= N;y++) {
  74. 		int t_idxx = N + 1;//들어온 원소 수라고 생각 최초는 empthy
  75.  
  76. 		for (int x = N; x >= 1;x--) {
  77.  
  78. 			if (board[x][y] == 0) continue;
  79.  
  80. 			//board[x][y]에 뭔가 있을때..
  81. 			if (t_idxx > N) {//처음껀 그냥 옮겨주고
  82. 				t_idxx--;
  83. 				temp[t_idxx][y] = board[x][y];
  84. 			}
  85. 			else {//나머지의 경우는 같은거 있는지 검사
  86. 				if (temp[t_idxx][y] == board[x][y] && canjoin[t_idxx][y] == 0) {
  87. 					temp[t_idxx][y] = temp[t_idxx][y] * 2;
  88. 					//t_idxx는 그대로 유지
  89. 					canjoin[t_idxx][y] = 1;
  90. 				}
  91. 				else {
  92. 					t_idxx--;
  93. 					temp[t_idxx][y] = board[x][y];
  94. 				}
  95. 			}
  96. 		}
  97. 		t_idxx--;
  98. 		while( t_idxx >= 1)	temp[t_idxx--][y] = 0;
  99. 	}
  100. }
  101.  
  102.  
  103. void left( int board[21][21], int temp[21][21])
  104. {
  105. 	int canjoin[21][21] = { 0, };//yes가 0 no가 1
  106.  
  107. 	for (int x = 1; x <= N;x++) {
  108. 		int t_idxx = 0;//들어온 원소 수라고 생각 최초는 empthy
  109.  
  110. 		for (int y = 1; y <= N;y++) {
  111.  
  112. 			if (board[x][y] == 0) continue;
  113.  
  114. 			//board[x][y]에 뭔가 있을때..
  115. 			if (t_idxx == 0) {//처음껀 그냥 옮겨주고
  116. 				t_idxx++;
  117. 				temp[x][t_idxx] = board[x][y];
  118. 			}
  119. 			else {//나머지의 경우는 같은거 있는지 검사
  120. 				if (temp[x][t_idxx] == board[x][y] && canjoin[x][t_idxx] == 0) {
  121. 					temp[x][t_idxx] = temp[x][t_idxx] * 2;
  122. 					//t_idxx는 그대로 유지
  123. 					canjoin[x][t_idxx] = 1;
  124. 				}
  125. 				else {
  126. 					t_idxx++;
  127. 					temp[x][t_idxx] = board[x][y];
  128. 				}
  129. 			}
  130. 		}
  131. 		t_idxx++;
  132. 		while( t_idxx <= N)	temp[x][t_idxx++] = 0;
  133. 	}
  134. }
  135.  
  136. void right( int board[21][21], int temp[21][21])
  137. {
  138. 	int canjoin[21][21] = { 0, };//yes가 0 no가 1
  139.  
  140. 	for (int x = 1; x <= N;x++) {
  141. 		int t_idxx = N + 1;//들어온 원소 수라고 생각 최초는 empthy
  142.  
  143. 		for (int y = N; y >= 1; y--) {
  144.  
  145. 			if (board[x][y] == 0) continue;
  146.  
  147. 			//board[x][y]에 뭔가 있을때..
  148. 			if (t_idxx > N) {//처음껀 그냥 옮겨주고
  149. 				t_idxx--;
  150. 				temp[x][t_idxx] = board[x][y];
  151. 			}
  152. 			else {//나머지의 경우는 같은거 있는지 검사
  153. 				if (temp[x][t_idxx] == board[x][y] && canjoin[x][t_idxx] == 0) {
  154. 					temp[x][t_idxx] = temp[x][t_idxx] * 2;
  155. 					//t_idxx는 그대로 유지
  156. 					canjoin[x][t_idxx] = 1;
  157. 				}
  158. 				else {
  159. 					t_idxx--;
  160. 					temp[x][t_idxx] = board[x][y];
  161. 				}
  162. 			}
  163. 		}
  164. 		t_idxx--;
  165. 		while( t_idxx >= 1)	temp[x][t_idxx--] = 0;
  166. 	}
  167. }
  168.  
  169.  
  170. //동치 분석으로 인한 bfs코드
  171. void dfs( int count, int board[21][21]) 
  172. {
  173. 	int outboard[21][21] = {0};
  174.  
  175. 	if (count == 5) 
  176. 	{//재귀의 탈출조건(중요)
  177. 		int candi = find_max( board);
  178. 		ans = MAX(ans, candi);
  179.  
  180. 		return;
  181. 	}
  182.  
  183.  
  184. 	for (int i = 1;i <= 4; i++) //1=상, 2=하, 3=좌, 4=우
  185. 	{
  186. 		switch(i)
  187. 		{
  188. 		case 1:
  189. 			up( board, outboard);
  190. 			break;
  191. 		case 2:
  192. 			down( board, outboard);
  193. 			break;
  194. 		case 3:
  195. 			left( board, outboard);
  196. 			break;
  197. 		case 4:
  198. 			right( board, outboard);
  199. 			break;
  200. 		default:
  201. 			break;
  202. 		}
  203. 		dfs(count + 1, outboard);
  204. 	}
  205. }
  206.  
  207. void print_board( int board[21][21])
  208. {
  209. 	for (int x = 1; x <= N; x++) 
  210. 	{
  211. 		for (int y = 1; y <= N; y++) 
  212. 		{
  213. 			cout << board[x][y] << ' ';
  214. 		}
  215. 		cout << '\n';
  216. 	}
  217. }
  218.  
  219. int main( void)  
  220. {
  221. 	int board[21][21];
  222.  
  223. 	cin >> N;
  224. 	for (int x = 1; x <= N;x++)
  225. 	for (int y = 1; y <= N;y++)
  226. 	{
  227. 		cin >> board[x][y];
  228. 	}
  229.  
  230. 	dfs( 0, board);
  231. 	cout << ans;
  232.  
  233. 	return 0;
  234. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3
2 2 2
4 4 4
8 8 8
stdout
copy 
16
https://ideone.com/9MDG7L
2048 수정 버전
language:
C++14 (gcc 8.3)
created:
6 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!