3085 사탕 게임
이 문제는 일단 전부 교체해보지 않는한 최대값을 알수 없는 문제가 있다.
결국 브루트 포스 문제이다.
답은 아래와 같다.
|
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
|
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
char map[50][50];
int n;
int Max = 0;
bool isRange(int y, int x) {
return y < n && y >= 0 && x >= 0 && x < n;
}
void totalEatCount(int y, int x,int eat) {
int temp = 1;
for (int ly = y–1; isRange(ly, x); ly––) {
if (map[ly][x] != eat) break;
temp++;
}
for (int ry = y+1; isRange(ry, x); ry++) {
if (map[ry][x] != eat) break;
temp++;
}
Max = std::max(temp, Max);
temp = 1;
for (int lx = x–1; isRange(y, lx); lx––) {
if (map[y][lx] != eat) break;
temp++;
}
for (int tx = x+1; isRange(y, tx); tx++) {
if (map[y][tx] != eat) break;
temp++;
}
Max = std::max(temp, Max);
}
void impEat(int y,int x,int chy,int chx) {
std::swap(map[y][x], map[chy][chx]);
totalEatCount(y, x,map[y][x]);
std::swap(map[y][x], map[chy][chx]);
}
void eat(int y,int x) {
// 상하좌우
int max = 0;
if (isRange(y – 1, x)) {
impEat(y, x, y – 1, x);
}
if (isRange(y + 1, x)) {
impEat(y, x, y + 1, x);
}
if (isRange(y, x +1)) {
impEat(y, x, y , x + 1);
}
if (isRange(y, x –1)) {
impEat(y, x, y, x – 1);
}
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
std::cin >> map[i][j];
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
eat(i, j);
}
}
std::cout << Max << std::endl;
}
|
cs |