[BOJ] 1917 정육면체 전개도

Time Lapse :1hour 2min 31sec

1917.cpp

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
#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
int map[6][6];
int sq1[44][6][6] = {
{{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,1,0},{0,1,1,1,1,0},{0,0,0,1,0,0},{0,0,0,0,0,0}},
{{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,1,0},{0,1,1,1,1,0},{0,0,1,0,0,0},{0,0,0,0,0,0}},
{{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,1,0},{0,1,1,1,1,0},{0,1,0,0,0,0},{0,0,0,0,0,0}},
{{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,1,0,0},{0,1,1,1,1,0},{0,0,0,1,0,0},{0,0,0,0,0,0}},
{{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,1,0,0},{0,1,1,1,1,0},{0,0,1,0,0,0},{0,0,0,0,0,0}},
{{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,1,1,0},{0,1,1,1,0,0},{0,0,1,0,0,0},{0,0,0,0,0,0}},
{{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,1,1,1},{0,1,1,1,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0}},
{{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,1,1,0},{0,1,1,1,0,0},{0,0,0,1,0,0},{0,0,0,0,0,0}},
{{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,1,1,0},{0,1,1,1,0,0},{0,1,0,0,0,0},{0,0,0,0,0,0}},
{{0,0,0,0,0,0},{0,0,0,1,1,0},{0,0,1,1,0,0},{0,1,1,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0}},
{{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,1,0},{0,1,1,1,1,0},{0,0,0,0,1,0},{0,0,0,0,0,0}},
}, sq2[44][6][6], sq3[44][6][6], sq4[44][6][6];
bool equal(int movedMap[6][6]) {
for(int k = 0; k < 44; k++) {
int f1 = 0, f2 = 0, f3 = 0, f4 =0;
for (int i = 0; i < 6; i++)
for (int j = 0; j < 6; j++) {
if(movedMap[i][j]) {
if(sq1[k][i][j]) ++f1;
if(sq2[k][i][j]) ++f2;
if(sq3[k][i][j]) ++f3;
if(sq4[k][i][j]) ++f4;
}
}
if(f1 == 6 || f2 == 6 || f3 == 6 || f4 == 6)
return true;
}
return false;
}
bool chk() {
int top = 99, bottom = -1, left = 99, right = -1;
int movedMap[6][6];
for(int i = 0; i < 6; i++)
for(int j = 0; j < 6; j++)
if(map[i][j]) {
top = min(top, i);
bottom = max(bottom, i);
left = min(left, j);
right = max(right, j);
}
for(int i = 0; i < 6; i++)
for(int j = 0; j < 6; j++)
if(map[i][j])
swap(map[i][j], map[i-top][j-left]);
bottom -= top; right -= left;
for(int i = 0; i < 6 - bottom; i++) {
for (int j = 0; j < 6 - right; j++) {
memset(movedMap, 0, sizeof(movedMap));
for(int k = 0; k < 6; k++)
for(int l = 0; l < 6; l++)
if(map[k][l])
movedMap[k+i][l+j] = 1;
if(equal(movedMap))
return true;
}
}
return false;
}
int main() {
for(int k = 11; k < 22; k++)
for(int i = 0; i < 6; i++)
for(int j = 0; j < 6; j++)
sq1[k][i][j] = sq1[k-11][i][6-j];
for(int k = 22; k < 44; k++)
for(int i = 0; i < 6; i++)
for(int j = 0; j < 6; j++)
sq1[k][i][j] = sq1[k-22][6-i][6-j];
for(int k = 0; k < 44; k++)
for(int i = 0; i < 6; i++)
for(int j = 0; j < 6; j++) {
sq2[k][j][i] = sq1[k][i][j];
sq3[k][i][j] = sq1[k][6 - i][6 - j];
sq4[k][j][i] = sq3[k][i][j];
}
for (int k = 0; k < 3; k++) {
for (int i = 0; i < 6; i++)
for (int j = 0; j < 6; j++)
scanf("%d", &map[i][j]);
printf("%s\n",chk() ? "yes" : "no");
}
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2020/09/06/PS/BOJ/1917/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.