728x90
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
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
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
/*
문제 파악
- 맵의 크기와 맵이 입력으로 주어진다. 맵은 정수형 숫자로 이루어져 있다.
- 도형 5개가 주어진다. 도형은 회전, 대칭이 가능하다
- 테트로미노 하나를 적절히 놓아서 테트로미노가 놓은 보드의 값의 최대를 출력하는 문제
---------------------------------------------------------------------------------
문제 해결 방안:
- 블록을 회전 또는 대칭 할 수 있는 모든 경우를 미리 만들어 놓는다.
- 500 x 500 보드판에 그대로 놓고 한 칸씩 올겨 가면서 비교.
*/
#include <iostream>
using namespace std;
int n, m;
int map[503][503];
//왼쪽 위에 도형을 붙여 넣음 : 기준점을 생성
const char block[19][4][5] = {
{
"1111",
"0000",
"0000",
"0000",
},
{
"1000",
"1000",
"1000",
"1000",
},
{
"1100",
"1100",
"0000",
"0000",
},
{
"1110",
"1000",
"0000",
"0000",
},
{
"1100",
"0100",
"0100",
"0000",
},
{
"1000",
"1000",
"1100",
"0000",
},
{
"0010",
"1110",
"0000",
"0000",
},
{
"0100",
"0100",
"1100",
"0000",
},
{
"1000",
"1110",
"0000",
"0000",
},
{
"1100",
"1000",
"1000",
"0000",
},
{
"1110",
"0010",
"0000",
"0000",
},
{
"1000",
"1100",
"0100",
"0000",
},
{
"0110",
"1100",
"0000",
"0000",
},
{
"0100",
"1100",
"1000",
"0000",
},
{
"1100",
"0110",
"0000",
"0000",
},
{
"1110",
"0100",
"0000",
"0000",
},
{
"0100",
"1100",
"0100",
"0000",
},
{
"0100",
"1110",
"0000",
"0000",
},
{
"1000",
"1100",
"1000",
"0000",
},
};
int get_count(int sy, int sx, int k){
int ret = 0;
for(int y = 0; y < 4; y++){
for(int x = 0; x < 4; x++){
ret += (block[k][y][x] - '0') * map[sy + y][sx + x];
}
}
return ret;
}
int main(){
cin>>n>>m;
//맵 정보를 받는다.
for(int y = 0; y < n; y++){
for(int x = 0; x <m; x++){
cin>>map[y][x];
}
}
//입력 받은 맵에서 아래로 세 칸 매우 작은 값을 추가해 준다.
for(int y = n; y <n + 3; y++){
for (int x = 0; x < m + 3; x++){
map[y][x] = -100000;
}
}
//입력 받은 맵에서 오른쪽으로 세 칸 매우 작은 값을 추가해 준다.
for(int y = 0; y < n + 3; y++){
for (int x= m; x < m + 3; x++){
map[y][x] = -100000;
}
}
int ret = 0;
for (int y = 0; y < n; y++){
for (int x = 0; x < m; x++){
for (int k = 0; k < 19; k++){ //도형 19개
int candi = get_count(y, x, k); //시작점에 y, x 좌표를 넣어주고 어떤 블록을 체크 할 건지 넣어줌
//블록이 그 위치에 있을 때 얻을 수 있는 candi 값을 넣어줌
if (ret < candi){
ret = candi;
}
}
}
}
cout<<ret<<endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
(1) 도형을 미리 만들어 준 뒤 맵으로 부터 시작점 y, x와 체크 할 도형 k 로하여 get_count(y, x, k) 함수를 호출한다.
(2) 도형은 4 X 4 맵에 있으므로 0~4까지 도는 이중 반목문을 돌려준다.
(3) ret 라는 변수에 점수 값을 누적하여 더해주고 그 값을 candi 에 반환한다.
(4) 변수 candi 가 받은 값중 최대값을 구하여 출력한다.
get_count() 함수를 잘 이용하면 도형이 나오는 문제가 나왔을 때 잘 이용 할 수 있을 거 같은 느낌이 든다.
728x90
'Algorithm Study > BOJ with C++' 카테고리의 다른 글
| (BAEKJOON) 14891번: 톱니바퀴 (0) | 2020.04.20 |
|---|---|
| (BAEKJOON) 13458번: 시험 감독 (0) | 2020.04.18 |
| (BAEKJOON) 14499번: 주사위 굴리기 (0) | 2020.04.17 |
| (BAEKJOON) 12100번: 2048(Easy) (0) | 2020.04.16 |
| (BAEKJOON) 3190번: 뱀 (0) | 2020.04.16 |
댓글