백준12094 2048 (Hard)

작성일 | In

문제 링크

  • http://icpc.me/12094

사용 알고리즘

  • 브루트 포스

풀이

Easy 문제 풀이에서 이어집니다.
최대 연산 횟수가 늘어났기 때문에 커팅을 조금 해야합니다.

두 가지 커팅만 해주면 AC를 받을 수 있습니다.

앞으로 K번의 이동을 더 할 수 있는데, 현재 상태에서의 최댓값이 $M / 2^K$보다 작으면 아무리 열심히 합쳐도 M보다 커질 수 없습니다. 이런 경우는 탐색할 필요가 없으므로 가지치기를 해줍니다.

특정 방향으로 이동을 했는데 보드판의 상태가 바뀌지 않았다면 재귀호출을 할 필요가 없습니다. 이런 경우에도 커팅을 해줍니다.

위 두 가지 커팅만 해주면 문제를 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
using namespace std;

int n, mx;
int inp[22][22];

namespace Solve{
	int arr[22][22];

	int get(){
		int ret = 0;
		for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) ret = max(ret, arr[i][j]);
		return ret;
	}

	void up(){
		queue<int> q;
		for(int j=1; j<=n; j++){
			for(int i=1; i<=n; i++){
				if(arr[i][j]) q.push(arr[i][j]), arr[i][j] = 0;
			}
			int t = 1;
			while(q.size()){
				int now = q.front(); q.pop();
				if(arr[t][j] == 0) arr[t][j] = now;
				else if(arr[t][j] == now) arr[t++][j] *= 2;
				else arr[++t][j] = now;
			}
		}
	}

	void dw(){
		queue<int> q;
		for(int j=1; j<=n; j++){
			for(int i=n; i>=1; i--){
				if(arr[i][j]) q.push(arr[i][j]), arr[i][j] = 0;
			}
			int t = n;
			while(q.size()){
				int now = q.front(); q.pop();
				if(arr[t][j] == 0) arr[t][j] = now;
				else if(arr[t][j] == now) arr[t--][j] *= 2;
				else arr[--t][j] = now;
			}
		}
	}

	void le(){
		queue<int> q;
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				if(arr[i][j]) q.push(arr[i][j]), arr[i][j] = 0;
			}
			int t = 1;
			while(q.size()){
				int now = q.front(); q.pop();
				if(arr[i][t] == 0) arr[i][t] = now;
				else if(arr[i][t] == now) arr[i][t++] *= 2;
				else arr[i][++t] = now;
			}
		}
	}

	void ri(){
		queue<int> q;
		for(int i=1; i<=n; i++){
			for(int j=n; j>=1; j--){
				if(arr[i][j]) q.push(arr[i][j]), arr[i][j] = 0;
			}
			int t = n;
			while(q.size()){
				int now = q.front(); q.pop();
				if(arr[i][t] == 0) arr[i][t] = now;
				else if(arr[i][t] == now) arr[i][t--] *= 2;
				else arr[i][--t] = now;
			}
		}
	}

	void go(int x){
		if(x == 0) up();
		if(x == 1) dw();
		if(x == 2) le();
		if(x == 3) ri();
	}
};
using namespace Solve;

void solve();

void dfs(int idx){
	if(idx == 10){
		mx = max(mx, get());
	}
	if(get() * (1 << 10-idx) <= mx) return;
	int now[22][22];
	memcpy(now, arr, sizeof now);
	for(int k=0; k<4; k++){
		go(k);
		int flag = 0;
		for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(arr[i][j] != now[i][j]){
			flag = 1; break;
		}
		if(flag) dfs(idx+1);
		memcpy(arr, now, sizeof arr);
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin >> inp[i][j];

	memcpy(arr, inp, sizeof arr);
	mx = max(mx, get());
	dfs(0);
	cout << mx;
}