fork(1) 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 board[21][21];
  20. int backup_board[21][21];
  21.  
  22. int ans=-oo;
  23.  
  24. int find_max() {
  25. 	int ret = -oo;
  26. 	for (int x = 1; x <= N;x++) {
  27. 		for (int y = 1; y <= N; y++) {
  28. 			ret = MAX(ret, board[x][y]);
  29. 		}
  30. 	}
  31. 	return ret;
  32. }
  33.  
  34. //조건 해석하기
  35. void up() {
  36. 	int temp[21][21] = { 0, };
  37. 	int canjoin[21][21] = { 0, };//yes가 0 no가 1
  38.  
  39. 	for (int y = 1; y <= N;y++) {
  40. 		int t_idxx = 0;//들어온 원소 수라고 생각 최초는 empthy
  41.  
  42. 		for (int x = 1; x <= N;x++) {
  43.  
  44. 			if (board[x][y] == 0) continue;
  45.  
  46. 			//board[x][y]에 뭔가 있을때..
  47. 			if (t_idxx == 0) {//처음껀 그냥 옮겨주고
  48. 				t_idxx++;
  49. 				temp[t_idxx][y] = board[x][y];
  50. 			}
  51. 			else {//나머지의 경우는 같은거 있는지 검사
  52. 				if (temp[t_idxx][y] == board[x][y] && canjoin[t_idxx][y] == 0) {
  53. 					temp[t_idxx][y] = temp[t_idxx][y] * 2;
  54. 					//t_idxx는 그대로 유지
  55. 					canjoin[t_idxx][y] = 1;
  56. 				}
  57. 				else {
  58. 					t_idxx++;
  59. 					temp[t_idxx][y] = board[x][y];
  60. 				}
  61. 			}
  62. 		}
  63. 	}
  64.  
  65. 	//마지막으로 복사해주고 끝
  66. 	for (int x = 1;x <= N;x++) {
  67. 		for (int y = 1; y <= N; y++) {
  68. 			board[x][y] = temp[x][y];
  69. 		}
  70. 	}
  71. }
  72.  
  73. void down() {
  74. 	int temp[21][21] = { 0, };
  75. 	int canjoin[21][21] = { 0, };//yes가 0 no가 1
  76.  
  77. 	for (int y = 1; y <= N;y++) {
  78. 		int t_idxx = N + 1;//들어온 원소 수라고 생각 최초는 empthy
  79.  
  80. 		for (int x = N; x >= 1;x--) {
  81.  
  82. 			if (board[x][y] == 0) continue;
  83.  
  84. 			//board[x][y]에 뭔가 있을때..
  85. 			if (t_idxx > N) {//처음껀 그냥 옮겨주고
  86. 				t_idxx--;
  87. 				temp[t_idxx][y] = board[x][y];
  88. 			}
  89. 			else {//나머지의 경우는 같은거 있는지 검사
  90. 				if (temp[t_idxx][y] == board[x][y] && canjoin[t_idxx][y] == 0) {
  91. 					temp[t_idxx][y] = temp[t_idxx][y] * 2;
  92. 					//t_idxx는 그대로 유지
  93. 					canjoin[t_idxx][y] = 1;
  94. 				}
  95. 				else {
  96. 					t_idxx--;
  97. 					temp[t_idxx][y] = board[x][y];
  98. 				}
  99. 			}
  100. 		}
  101. 	}
  102.  
  103. 	//마지막으로 복사해주고 끝
  104. 	for (int x = 1;x <= N;x++) {
  105. 		for (int y = 1; y <= N; y++) {
  106. 			board[x][y] = temp[x][y];
  107. 		}
  108. 	}
  109. }
  110.  
  111.  
  112. void left() {
  113. 	int temp[21][21] = { 0, };
  114. 	int canjoin[21][21] = { 0, };//yes가 0 no가 1
  115.  
  116.  
  117. 	for (int x = 1; x <= N;x++) {
  118. 		int t_idxx = 0;//들어온 원소 수라고 생각 최초는 empthy
  119.  
  120. 		for (int y = 1; y <= N;y++) {
  121.  
  122. 			if (board[x][y] == 0) continue;
  123.  
  124. 			//board[x][y]에 뭔가 있을때..
  125. 			if (t_idxx == 0) {//처음껀 그냥 옮겨주고
  126. 				t_idxx++;
  127. 				temp[x][t_idxx] = board[x][y];
  128. 			}
  129. 			else {//나머지의 경우는 같은거 있는지 검사
  130. 				if (temp[x][t_idxx] == board[x][y] && canjoin[x][t_idxx] == 0) {
  131. 					temp[x][t_idxx] = temp[x][t_idxx] * 2;
  132. 					//t_idxx는 그대로 유지
  133. 					canjoin[x][t_idxx] = 1;
  134. 				}
  135. 				else {
  136. 					t_idxx++;
  137. 					temp[x][t_idxx] = board[x][y];
  138. 				}
  139. 			}
  140. 		}
  141. 	}
  142.  
  143. 	//마지막으로 복사해주고 끝
  144. 	for (int x = 1;x <= N;x++) {
  145. 		for (int y = 1; y <= N; y++) {
  146. 			board[x][y] = temp[x][y];
  147. 		}
  148. 	}
  149. }
  150.  
  151. void right() {
  152. 	int temp[21][21] = { 0, };
  153. 	int canjoin[21][21] = { 0, };//yes가 0 no가 1
  154.  
  155. 	for (int x = 1; x <= N;x++) {
  156. 		int t_idxx = N + 1;//들어온 원소 수라고 생각 최초는 empthy
  157.  
  158. 		for (int y = N; y >= 1; y--) {
  159.  
  160. 			if (board[x][y] == 0) continue;
  161.  
  162. 			//board[x][y]에 뭔가 있을때..
  163. 			if (t_idxx > N) {//처음껀 그냥 옮겨주고
  164. 				t_idxx--;
  165. 				temp[x][t_idxx] = board[x][y];
  166. 			}
  167. 			else {//나머지의 경우는 같은거 있는지 검사
  168. 				if (temp[x][t_idxx] == board[x][y] && canjoin[x][t_idxx] == 0) {
  169. 					temp[x][t_idxx] = temp[x][t_idxx] * 2;
  170. 					//t_idxx는 그대로 유지
  171. 					canjoin[x][t_idxx] = 1;
  172. 				}
  173. 				else {
  174. 					t_idxx--;
  175. 					temp[x][t_idxx] = board[x][y];
  176. 				}
  177. 			}
  178. 		}
  179. 	}
  180.  
  181. 	//마지막으로 복사해주고 끝
  182. 	for (int x = 1;x <= N;x++) {
  183. 		for (int y = 1; y <= N; y++) {
  184. 			board[x][y] = temp[x][y];
  185. 		}
  186. 	}
  187. }
  188.  
  189.  
  190. //동치 분석으로 인한 bfs코드
  191. void dfs(int count) 
  192. {
  193. 	int backup_board[21][21] = {0};
  194. 	memcpy(backup_board, board, sizeof(board));
  195.  
  196. 	if (count == 5) {//재귀의 탈출조건(중요)
  197. 		int candi = find_max();
  198. 		ans = MAX(ans, candi);
  199.  
  200. 		memcpy(board, backup_board, sizeof(backup_board));
  201. 		return;
  202. 	}
  203.  
  204.  
  205. 	for (int i = 1;i <= 4;i++) //1=상, 2=하, 3=좌, 4=우
  206. 	{
  207. 		switch (i)
  208. 		{
  209. 		case 1:
  210. 			up();
  211. 			break;
  212. 		case 2:
  213. 			down();
  214. 			break;
  215. 		case 3:
  216. 			left();
  217. 			break;
  218. 		case 4:
  219. 			right();
  220. 			break;
  221. 		default:
  222. 			break;
  223. 		}
  224. 		dfs(count + 1);
  225. 		memcpy(board, backup_board, sizeof(backup_board));
  226. 	}
  227. }
  228.  
  229. void print_board( void)
  230. {
  231. 	for (int x = 1; x <= N; x++) 
  232. 	{
  233. 		for (int y = 1; y <= N; y++) 
  234. 		{
  235. 			cout << board[x][y] << ' ';
  236. 		}
  237. 		cout << '\n';
  238. 	}
  239. }
  240.  
  241. void reset( void)
  242. {
  243. 	for (int x = 1; x <= N; x++) 
  244. 	{
  245. 		for (int y = 1; y <= N; y++) 
  246. 		{
  247. 			board[x][y] = backup_board[x][y];
  248. 		}
  249. 	}
  250. }
  251.  
  252.  
  253. int main() {
  254. 	cin >> N;
  255. 	for (int x = 1; x <= N;x++) {
  256. 		for (int y = 1; y <= N;y++) {
  257. 			cin >> board[x][y];
  258. 			backup_board[x][y] = board[x][y];
  259. 		}
  260. 	}
  261.  
  262. 	int count = 0;
  263. 	dfs(count);
  264.  
  265. 	cout << ans;
  266. 	return 0;
  267. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3
2 2 2
4 4 4
8 8 8
stdout
copy 
16
https://ideone.com/kKUJDx
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!