#define BLOCK_SIZE 30000
#ifndef UINT
#define UINT unsigned int
#endif
#define Move(x, from, to) \
((x >> from & 3) << to)
#define Change(x, \
a30, a28, a26, a24, \
a22, a20, a18, a16, \
a14, a12, a10, a8, \
a6, a4, a2, a0) \
(\
Move(x, a30, 30) | Move(x, a28, 28) | Move(x, a26, 26) | Move(x, a24, 24) |
Move(x, a22, 22) | Move(x, a20, 20) | Move(x, a18, 18) | Move(x, a16, 16) |
Move(x, a14, 14) | Move(x, a12, 12) | Move(x, a10, 10) | Move(x, a8, 8) |
Move(x, a6, 6) | Move(x, a4, 4) | Move(x, a2, 2) | Move(x, a0, 0)
)
class Block {
public:
UINT shape;
int height;
int depth;
Block() {
shape = height = depth = 0;
}
};
Block set0[BLOCK_SIZE], set1[BLOCK_SIZE], set2[BLOCK_SIZE];
int cnt0, cnt1, cnt2;
void init() {
cnt0 = cnt1 = cnt2 = 0;
}
#define HASH_MODULAR 33333
#define HASH_TABLE_SIZE 70000
#define HASH_BUCKET_SIZE 10
UINT HShape[HASH_TABLE_SIZE];
int HashCnt[HASH_TABLE_SIZE];
int HashTable[HASH_TABLE_SIZE][HASH_BUCKET_SIZE];
void initHash() {
for (int i = 0; i < HASH_TABLE_SIZE; ++i) {
HShape[i] = HashCnt[i] = 0;
}
}
void addHash(UINT shape, int value) {
int key = ((shape >> 16) % HASH_MODULAR) + (shape % HASH_MODULAR);
while (HShape[key] != shape && HShape[key] != 0) {
key = (key + 1) % HASH_TABLE_SIZE;
// shape 에 해당하는 key 가 이미 사용중일 경우,
// 1씩 key 값을 증가시키며 할당되지 않은 key 를 탐색
}
HShape[key] = shape;
HashTable[key][HashCnt[key]++] = value;
}
int removeHash(UINT shape) {
int key = ((shape >> 16) % HASH_MODULAR) + (shape % HASH_MODULAR);
while (HShape[key] != shape) {
if (HShape[key] == 0)
return -1; // 일치하는 모양이 없음.
key = (key + 1) % HASH_TABLE_SIZE;
// shape 에 해당하는 key 를 찾기 위해 1씩 key 값을 증가시키며 탐색
}
if (HashCnt[key] == 0)
return -1; // 일치하는 모양의 블록을 다 사용하였음.
int maxIdx = 0;
for (int i = 1; i < HashCnt[key]; i++) {
if (HashTable[key][maxIdx] < HashTable[key][i])
maxIdx = i;
}
int maxValue = HashTable[key][maxIdx];
HashTable[key][maxIdx] = HashTable[key][HashCnt[key] - 1];
HashCnt[key]--;
return maxValue;
}
void makeBlock(int info[4][4]) {
Block b;
int max = 0;
int min = 10;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (max < info[i][j])
max = info[i][j];
if (min > info[i][j])
min = info[i][j];
}
}
b.height = min;
b.depth = max - min;
int k = 30;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++, k -= 2) {
b.shape |= ((info[i][j] - min) << k);
}
}
// 4 방향 돌리면서 더 큰 숫자로 셋팅함.
// 1. 초기 상태의 모습
// 30 28 26 24
// 22 20 18 16
// 14 12 10 08
// 06 04 02 00
UINT tmpShape, originShape = b.shape;
// 2. 90도 회전
tmpShape = Change(originShape,
6, 14, 22, 30,
4, 12, 20, 28,
2, 10, 18, 26,
0, 8, 16, 24
);
if (tmpShape > b.shape)
b.shape = tmpShape;
// 3. 180도 회전
tmpShape = Change(originShape,
0, 2, 4, 6,
8, 10, 12, 14,
16, 18, 20, 22,
24, 26, 28, 30
);
if (tmpShape > b.shape)
b.shape = tmpShape;
// 4. 270도 회전
tmpShape = Change(originShape,
24, 16, 8, 0,
26, 18, 10, 2,
28, 20, 12, 4,
30, 22, 14, 6
);
if (tmpShape > b.shape)
b.shape = tmpShape;
if (b.depth == 2) {
set2[cnt2++] = b;
} else if (b.depth == 1) {
set1[cnt1++] = b;
} else {
set0[cnt0++] = b;
}
}
int getMaxMachedBlock(const UINT srcShape) {
UINT target_shape;
UINT shape[4];
// 4 방향 타겟을 구한 뒤, 제일 큰 모양으로 탐색을 함.
// 1. 초기 상태의 모습
// 30 28 26 24 | 24 26 28 30
// 22 20 18 16 | 16 18 20 22
// 14 12 10 08 | 08 10 12 14
// 06 04 02 00 | 00 02 04 06
shape[0] = Change(srcShape,
24, 26, 28, 30,
16, 18, 20, 22,
8, 10, 12, 14,
0, 2, 4, 6
);
// 2. 90도 회전
// 06 14 22 30 | 30 22 14 06
// 04 12 20 28 | 28 20 12 04
// 02 10 18 26 | 26 18 10 02
// 00 08 16 24 | 24 16 08 00
shape[1] = Change(srcShape,
30, 22, 14, 6,
28, 20, 12, 4,
26, 18, 10, 2,
24, 16, 8, 0
);
// 3. 180도 회전
// 00 02 04 06 | 06 04 02 00
// 08 10 12 14 | 14 12 10 08
// 16 18 20 22 | 22 20 18 16
// 24 26 28 30 | 30 28 26 24
shape[2] = Change(srcShape,
6, 4, 2, 0,
14, 12, 10, 8,
22, 20, 18, 16,
30, 28, 26, 24
);
// 4. 270도 회전
// 24 16 08 00 | 00 08 16 24
// 26 18 10 02 | 02 10 18 26
// 28 20 12 04 | 04 12 20 28
// 30 22 14 06 | 06 14 22 30
shape[3] = Change(srcShape,
0, 8, 16, 24,
2, 10, 18, 26,
4, 12, 20, 28,
6, 14, 22, 30
);
target_shape = shape[0];
for (int i = 1; i <= 3; i++) {
if (shape[i] > target_shape)
target_shape = shape[i];
}
return removeHash(target_shape);
}
int test(int module[][4][4]) {
init();
for (int i = 0; i < BLOCK_SIZE; i++)
makeBlock(module[i]);
int sum = 0;
// 1. 평평한 모양이면 짝수개로 다 더함.
for (int i = 0; i < cnt0; i++) {
sum += (set0[i].height);
}
if (cnt0 % 2) {
int minVal = 6;
// 홀수개 일 경우, 가장 작은 것 1개 제외
for (int i = 0; i < cnt0; i++) {
if (minVal > set0[i].height) {
minVal = set0[i].height;
}
}
sum -= minVal;
}
// 2. 높이차가 1이면, 두 블럭의 shape를 더한것이 0x55555555 가 되어야함.
// 0x55555555 = 01010101010101010101010101010101 (2)
initHash();
for (int i = 0; i < cnt1; i++)
addHash(set1[i].shape, set1[i].height);
for (int i = 0; i < cnt1 - 1; i++) {
int srcHeight = removeHash(set1[i].shape);
if (srcHeight < 0)
continue;
UINT srcShape = 0x55555555 - set1[i].shape;
int matchedHeight = getMaxMachedBlock(srcShape);
if (matchedHeight > 0)
sum += (srcHeight + matchedHeight + 1);
}
// 3. 높이차가 2이면, 두 블럭의 shape를 더한것이 0xaaaaaaaa 가 되어야함.
// 0xaaaaaaaa = 10101010101010101010101010101010 (2)
initHash();
for (int i = 0; i < cnt2; i++)
addHash(set2[i].shape, set2[i].height);
for (int i = 0; i < cnt2 - 1; i++) {
int srcHeight = removeHash(set2[i].shape);
if (srcHeight < 0)
continue;
UINT srcShape = ((UINT) 0xaaaaaaaa) - set2[i].shape;
int matchedHeight = getMaxMachedBlock(srcShape);
if (matchedHeight > 0)
sum += (srcHeight + matchedHeight + 2);
}
return sum;
}
댓글