반응형
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
|
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
|
// 한 쪽으로 옮기기
void move() {
int temp[21][21];
// 열 단위(세로줄)로 처리
rep(j, n) {
bool flag = 0; // 합칠 수 있는가?
int row = -1; // temp[][]의 현재 row
rep(i, n) {
if (arr[i][j] == 0) continue;
if (flag && arr[i][j] == temp[row][j]) { // 합칠 수 있음 + arr[i] == temp[row]
temp[row][j] *= 2; // 현재 row에서 합치기
flag = 0; // 합칠 수 없도록 변경
}
else {
temp[++row][j] = arr[i][j]; // 현재 row에서 못 합치므로, 다음 row로 이동
flag = 1; // 합칠 수 있도록 변경
}
}
for (int k = row + 1; k < n; k++) // 빈 칸 채우기
temp[k][j] = 0;
}
rep(i, n) {
rep(j, n)
arr[i][j] = temp[i][j];
}
}
|
cs |
|
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
|
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, ans;
struct board {
int arr[21][21];
// 90도 회전
void rotate() {
int temp[21][21];
rep(i, n) {
rep(j, n)
temp[i][j] = arr[n - j - 1][i];
}
rep(i, n) {
rep(j, n)
arr[i][j] = temp[i][j];
}
}
// 한 쪽으로 옮기기
void move() {
int temp[21][21];
// 열 단위(세로줄)로 처리
rep(j, n) {
bool flag = 0; // 합칠 수 있는가?
int row = -1; // temp[][]의 현재 row
rep(i, n) {
if (arr[i][j] == 0) continue;
if (flag && arr[i][j] == temp[row][j]) { // i: 계속 증가, row: 조건 맞으면 증가
temp[row][j] *= 2; // 현재 row에서 합치기
flag = 0;
}
else {
temp[++row][j] = arr[i][j]; // 현재 row에서 못 합치므로, 다음 row로 이동
flag = 1;
}
}
for (int k = row + 1; k < n; k++) // 빈 칸 채우기
temp[k][j] = 0;
}
rep(i, n) {
rep(j, n)
arr[i][j] = temp[i][j];
}
}
// 최댓값
int getMax() {
int ret = 0;
rep(i, n) {
rep(j, n)
ret = max(ret, arr[i][j]);
}
return ret;
}
};
void dfs(board b, int cnt) {
if (cnt == 5) {
ans = max(ans, b.getMax());
return;
}
rep(i, 4) {
// 원본을 이동시키면 안됨
board next = b;
next.move();
dfs(next, cnt + 1);
// 원본 회전시키기
b.rotate();
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
board b;
cin >> n;
rep(i, n) {
rep(j, n)
cin >> b.arr[i][j];
}
dfs(b, 0);
cout << ans;
}
|
cs |
반응형