14500번: 테트로미노
폴리오미노란 크기가 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
|
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
using std::vector;
typedef struct {
int x;
int y;
}objectpos;
typedef struct {
int x;
int y;
int direction;
}pos;
int main(int argc, char* argv[]) {
int n, m;
int** map;
int answer=0;
objectpos move[4] = { {-1,0},{0,1},{1,0},{0,-1} };
scanf("%d %d", &n, &m);
map = new int* [n];
for (int i = 0; i < n; i++) {
map[i] = new int[m];
for (int j = 0; j < m; j++) {
scanf("%d", &map[i][j]);
}
}
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
vector<pos> tetris;
int sum = map[x][y];
tetris.push_back({ x,y,-1 });
while (!tetris.empty()) {
tetris.back().direction++;
int posx = tetris.back().x + move[tetris.back().direction].x, posy = tetris.back().y + move[tetris.back().direction].y;
if (tetris.back().direction == 4 || tetris.size() == 4) {
sum -= map[tetris.back().x][tetris.back().y];
tetris.pop_back();
continue;
}
if (posx > n - 1 || posx<0 || posy>m - 1 || posy < 0) {
continue;
}
if (tetris.size() != 1 && tetris[tetris.size() - 2].direction == (tetris.back().direction + 2) % 4) {
continue;
}
tetris.push_back({ posx,posy,-1 });
sum += map[posx][posy];
if (sum > answer) {
answer = sum;
}
}
tetris.push_back({ x,y,-1 });
for (int i = 0; i < 4; i++) {
int posx = tetris.back().x + move[i].x, posy = tetris.back().y + move[i].y;
if (posx > n - 1 || posx<0 || posy>m - 1 || posy < 0) {
continue;
}
sum = map[x][y] + map[posx][posy];
posx = tetris.back().x + move[i].x + move[(i + 1) % 4].x;
posy = tetris.back().y + move[i].y + move[(i + 1) % 4].y;
if (posx > n - 1 || posx<0 || posy>m - 1 || posy < 0) {
continue;
}
sum += map[posx][posy];
posx = tetris.back().x + move[i].x + move[(i + 3) % 4].x;
posy = tetris.back().y + move[i].y + move[(i + 3) % 4].y;
if (posx > n - 1 || posx<0 || posy>m - 1 || posy < 0) {
continue;
}
sum += map[posx][posy];
if (sum > answer)
answer = sum;
}
}
}
printf("%d", answer);
for (int i = 0; i < n; i++) {
delete[] map[i];
}
delete[] map;
return 0;
}
|
실행시간이 생각보다 걸렸다. 나중에 다시 풀어봐야겠다.
'기타 코딩 > PS' 카테고리의 다른 글
| [백준] 가장 큰 정사각형 - 1915번 (0) | 2020.10.22 |
|---|---|
| [백준] 행렬 곱셈 순서 - 11049번 (0) | 2020.10.20 |
| [백준] 뱀 - 3190번 (0) | 2020.10.20 |
| [백준] 2048 (EASY) - 12100번 (0) | 2020.10.20 |
| [백준] 구슬 탈출2 - 13460번 (0) | 2020.10.20 |
