#include <iostream> #include <queue> #define MAX 25 using namespace std; int n; int map[MAX][MAX]; int ret; void merge(int d) { queue<int> q; int cnt = 0; switch (d) { case 0: for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (map[j][i] != 0) q.push(map[j][i]); map[j][i] = 0; } int idx = 0; int data = 0; while (!q.empty()) { data = q.front(); q.pop(); if (map[idx][i] == 0) map[idx][i] = data; else if (map[idx][i] == data) { map[idx][i] *= 2; idx++; } else map[++idx][i] = data; } } break; case 1: for (int i = 0; i < n; i++) { for (int j = n - 1; j >= 0; j--) { if (map[j][i] != 0) q.push(map[j][i]); map[j][i] = 0; } int idx = n - 1; int data; while (!q.empty()) { data = q.front(); q.pop(); if (map[idx][i] == 0) map[idx][i] = data; else if (map[idx][i] == data) { map[idx][i] *= 2; idx--; } else map[--idx][i] = data; } } break; case 2: for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (map[i][j] != 0) q.push(map[i][j]); map[i][j] = 0; } int idx = 0; int data; while (!q.empty()) { data = q.front(); q.pop(); if (map[i][idx] == 0) map[i][idx] = data; else if (map[i][idx] == data) { map[i][idx] *= 2; idx++; } else map[i][++idx] = data; } } break; case 3: for (int i = 0; i < n; i++) { for (int j = n - 1; j >= 0; j--) { if (map[i][j] != 0) q.push(map[i][j]); map[i][j] = 0; } int idx = n - 1; int data; while (!q.empty()) { data = q.front(); q.pop(); if (map[i][idx] == 0) map[i][idx] = data; else if (map[i][idx] == data) { map[i][idx] *= 2; idx--; } else map[i][--idx] = data; } } break; } } void copy(int(*a)[MAX], int(*b)[MAX]) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) a[i][j] = b[i][j]; } void dfs(int d) { if (d == 5) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (map[i][j] > ret) ret = map[i][j]; return; } int copymap[MAX][MAX]; copy(copymap, map); for (int i = 0; i < 4; i++) { merge(i); dfs(d + 1); copy(map, copymap); } } void input() { scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &map[i][j]); } int main() { input(); dfs(0); printf("%d\n", ret); return 0; } |
merge 함수, 동, 서, 남, 북 으로 돌렸을 때 map 이 어떻게 되는지 하나씩 구현 하였습니다. 여기서 큐를 사용하였습니다. 인덱스를 유념하여서 하나씩 만들어갑니다.
여기서도 dfs를 사용하기에 dfs를 사용 후에 dfs 사용전 값으로 돌려주기 위해서 copymap 함수를 만들었습니다. 그리고 dfs 내부를 들여다 봅니다.
여기서 return 될 때는 d가 5가 될때 입니다. 그리고 5가 된다면 모든 맵을 뒤져서 가장 큰 값을 찾아 냅니다. dfs를 돌리기전에 멀쩡한 copy 맵을 하나 가지고 있습니다. 그리고 dfs를 돌리기 위해서 한번 변경되고, d+1를 해줍니다. 오케이 이것은 마치, nx, ny 한번 바꾸고 나서 d+1 한 것과 마찬가지입니다. 어떤 변화를 주고 d+1 를 넣어주면 됩니다. 그리고 dfs(d+1) 이 끝나면 원래 정상적인 값으로 변경해주기 위해서 copymap 함수를 사용합니다. 오케이.
인풋함수 그대로 사용합니다. 오케이 좋았습니다. 처음 main 에서 dfs(0)은 아직 아무것도 하지 않은 dfs 입니다. 오케이 deep 이 0인 것입니다.