https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
테트로미노는 (ㅏ,ㅓ,ㅗ,ㅜ)를 제외하고 시작점으로부터 인접한 칸으로 세 번 더 이동한 모양이다.
예를 들어 밑의 그림에서 대충 저 1을 시작점으로 잡았다고 쳤을 때 아무렇게나 인접한 칸으로 네 번 이동하면
테트로미노가 된다. 즉, 모든 경우를 해보면 (ㅏ,ㅓ,ㅗ,ㅜ)를 제외한 모든 테트로미노를 만들 수 있다.
| 1 | 2 | ||||
| 3 | |||||
| 4 | |||||
| 1 | 2 | ||||
| 3 | 4 | ||||
모든 칸에서부터 시작하여 모든 종류의 테트로미노를 만들어주면 되는데
(ㅏ,ㅓ,ㅗ,ㅜ)는 밑에 코드처럼 따로 일일이 처리해주어야 한다.
ㅡ 에서 위아래로 튀어나온 부분(?)이랑 ㅣ 에서 좌우로 튀어나온 부분을 i, j로 놓고 그 나머지 부분을 추가적으로 더해줬다. 얘네도 범위를 벗어나지 않는다면 해당 네 칸을 더해준 다음에 최댓값과 각각 비교해주면 된다.
|
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
|
#include <iostream>
using namespace std;
int n, m;
int ans;
int map[500][500];
bool check[500][500];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void solve(int x, int y, int sum, int cnt) {
//테트로미노가 됐다!
if (cnt == 4) {
//최댓값을 비교하여 저장
if (ans < sum) ans = sum;
return;
}
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
//범위 체크
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
//방문하지 않았다면 방문
if (!check[nx][ny]) {
check[nx][ny] = true;
//sum에 현재 칸의 값을 더하여 넘겨준다. 현재칸을 선택했으므로 cnt도 증가
solve(nx, ny, sum + map[nx][ny], cnt + 1);
check[nx][ny] = false;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
}
}
//모든 칸에서 모든 테트로미노를 놓는 경우를 모두 해본다.
int sum;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
check[i][j] = true;
solve(i, j, map[i][j], 1);
check[i][j] = false;
//ㅏ
if (i - 1 >= 0 && i + 1 < n && j + 1 < m) {
sum = map[i][j];
sum += map[i - 1][j + 1] + map[i][j + 1] + map[i + 1][j + 1];
if (ans < sum) ans = sum;
}
//ㅗ
if (i - 1 >= 0 && j - 1 >= 0 && j + 1 < m) {
sum = map[i][j];
sum += map[i - 1][j - 1] + map[i - 1][j] + map[i - 1][j + 1];
if (ans < sum) ans = sum;
}
//ㅓ
if (i - 1 >= 0 && i + 1 < n && j - 1 >= 0) {
sum = map[i][j];
sum += map[i - 1][j - 1] + map[i][j - 1] + map[i + 1][j - 1];
if (ans < sum) ans = sum;
}
//ㅜ
if (i + 1 < n && j - 1 >= 0 && j + 1 < m) {
sum = map[i][j];
sum += map[i + 1][j - 1] + map[i + 1][j] + map[i + 1][j + 1];
if (ans < sum) ans = sum;
}
}
}
cout << ans << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 3190. 뱀 (0) | 2019.08.06 |
|---|---|
| [BOJ] 15683. 감시 (0) | 2019.08.05 |
| [BOJ] 14499. 주사위 굴리기 (0) | 2019.08.04 |
| [BOJ] 14503. 로봇 청소기 (0) | 2019.08.04 |
| [BOJ] 14502. 연구소 (0) | 2019.08.04 |