2 min read

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 = y1; 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 = x1; 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