2048 게임의 보드를 최대 10번 이동시켰을 때 가장 큰 블록을 구하는 문제입니다.
백트래킹 문제입니다.
최적화를 해줘야하는데 어떻게 줄여야 할지 한참 고민했네요…
2048(Easy)는 최대 5번 이동이라 모든 경우를 구해줘야 했지만 이 문제는 최대 10번이므로 가지치기를 해야합니다.
저는 2가지 경우에서 가지치기를 했습니다.
보드를 이동했지만, 전과 같다면 중복되는 상황이 있으므로 더 경우를 보지 않아도 됩니다.
현재 최대 블록이 4이고, 남은 이동 횟수가 3이라고 했을 때 얻을 수 있는 최댓값의 경우는 4를 3번 이동해서 32로 만들 경우입니다.
이를 이용하여 최대 점수를 구했지만 여태까지 구한 총 최댓값보다 작을 때 어차피 현재 상황은 정답을 구할 수 없으므로 더 이상 경우를 보지 않아도 됩니다.
나머지 구현은 2048(Easy)와 같이 하면 됩니다. 문제 그대로 보드가 움직이는 구현만 하면 됩니다.
시간 복잡도는 저도 잘 모르겠습니다…
저도 시간 측정하면서 최적화 해본거라…
배열대신 벡터를 사용했을 때 시간이 오래걸렸습니다
자세한 구현은 소스 코드를 참고하시면 될 것 같습니다!
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
using namespace std;
int main() {
int n; cin >> n;
int map[25][25] = {};
FOR(i, 1, n) FOR(j, 1, n) cin >> map[i][j];
auto move = [&](int d) {
if (d == 0) FOR(i, 1, n) {
int k = 1;
FOR(j, 1, n) {
if (!map[i][j]) continue;
map[i][k] = map[i][j++];
while (j <= n && !map[i][j]) j++;
if (j > n || map[i][k] != map[i][j]) k++, j--;
else map[i][k++] *= 2;
}
FOR(j, k, n) map[i][j] = 0;
}
if (d == 1) FOR(i, 1, n) {
int k = n;
RFOR(j, n, 1) {
if (!map[i][j]) continue;
map[i][k] = map[i][j--];
while (j > 0 && !map[i][j]) j--;
if (!j || map[i][k] != map[i][j]) k--, j++;
else map[i][k--] *= 2;
}
RFOR(j, k, 1) map[i][j] = 0;
}
if (d == 2) FOR(i, 1, n) {
int k = n;
RFOR(j, n, 1) {
if (!map[j][i]) continue;
map[k][i] = map[j--][i];
while (j > 0 && !map[j][i]) j--;
if (!j || map[k][i] != map[j][i]) k--, j++;
else map[k--][i] *= 2;
}
RFOR(j, k, 1) map[j][i] = 0;
}
if (d == 3) FOR(i, 1, n) {
int k = 1;
FOR(j, 1, n) {
if (!map[j][i]) continue;
map[k][i] = map[j++][i];
while (j <= n && !map[j][i]) j++;
if (j > n || map[k][i] != map[j][i]) k++, j--;
else map[k++][i] *= 2;
}
FOR(j, k, n) map[j][i] = 0;
}
int ret = 0;
FOR(i, 1, n) FOR(j, 1, n) ret = max(ret, map[i][j]);
return ret;
};
auto chk = [&](int temp[][25], int map[][25]) {
FOR(i, 1, n) FOR(j, 1, n)
if (temp[i][j] != map[i][j]) return 1;
return 0;
};
function <int(int, int)> dfs = [&](int lv, int Max) {
if (lv == 10)
return Max;
int temp[25][25] = {};
FOR(i, 1, n) FOR(j, 1, n) temp[i][j] = map[i][j];
FOR(i, 0, 3) {
int val = move(i);
if (val << (10 - lv - 1) > Max&& chk(temp, map))
Max = max(Max, dfs(lv + 1, max(Max, val)));
FOR(i, 1, n) FOR(j, 1, n) map[i][j] = temp[i][j];
}
return Max;
};
int Max = 0;
FOR(i, 1, n) FOR(j, 1, n)
Max = max(Max, map[i][j]);
cout << dfs(0, Max) << '\n';
return 0;
}