-
Notifications
You must be signed in to change notification settings - Fork 1
/
boj_18809.cpp
116 lines (106 loc) · 2.89 KB
/
boj_18809.cpp
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
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define WATER 0 // 물
#define NO 1 // 배양액 뿌릴 수 없는 곳
#define YES 2 // 배양액 뿌릴 수 있는 곳
#define RED 8 // 빨간 배양액
#define GREEN 9 // 초록 배양액
#define F 10 // 꽃
#define MAX 52
int N, M, G, R;
int total;
int board[MAX][MAX];
typedef struct {
int x;
int y;
}Point;
typedef struct {
int x;
int y;
int type;
int time;
}Info;
vector<Point> pos;
Info tmp_board[MAX][MAX];
int m_xy[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
int bfs(vector<int> arr) {
int answer = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
tmp_board[i][j].x = j; tmp_board[i][j].y = i;
tmp_board[i][j].time = 0; tmp_board[i][j].type = board[i][j];
}
}
int r_cnt = 0, g_cnt = 0;
queue<Info>q;
for (int i = 0; i < pos.size(); i++) {
if (arr[i] == RED) {
r_cnt++;
tmp_board[pos[i].y][pos[i].x].type = RED;
q.push(tmp_board[pos[i].y][pos[i].x]);
}
else if (arr[i] == GREEN) {
g_cnt++;
tmp_board[pos[i].y][pos[i].x].type = GREEN;
q.push(tmp_board[pos[i].y][pos[i].x]);
}
}
if (g_cnt != G || r_cnt != R) return 0;
while (!q.empty()) {
Info cur_pos = q.front();
q.pop();
if (tmp_board[cur_pos.y][cur_pos.x].type != F){
for (int i = 0; i < 4; i++) {
Info next_pos = { cur_pos.x + m_xy[i][0],cur_pos.y + m_xy[i][1],cur_pos.type,cur_pos.time + 1 };
//이동 불가능한 지역이라면 컨티뉴
if (next_pos.x < 0 || next_pos.y < 0 || next_pos.x >= M || next_pos.y >= N || tmp_board[next_pos.y][next_pos.x].type == WATER) continue;
//이동하려는 곳이 이동 가능한 곳이라면
if (tmp_board[next_pos.y][next_pos.x].type == NO || tmp_board[next_pos.y][next_pos.x].type == YES) {
tmp_board[next_pos.y][next_pos.x].type = next_pos.type;
tmp_board[next_pos.y][next_pos.x].time = next_pos.time;
q.push(next_pos);
}
//이동하려는 곳에 시간이 같고 타입이 서로 다르다면 꽃을 만든다.
else if (tmp_board[next_pos.y][next_pos.x].time == next_pos.time && ((next_pos.type == RED && tmp_board[next_pos.y][next_pos.x].type == GREEN) || (next_pos.type == GREEN && tmp_board[next_pos.y][next_pos.x].type == RED))) {
tmp_board[next_pos.y][next_pos.x].type = F;
tmp_board[next_pos.y][next_pos.x].time = next_pos.time;
answer++;
}
}
}
}
return answer;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> G >> R;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> board[i][j];
if (board[i][j] == YES) {
pos.push_back({ j,i });
}
}
}
total = G + R;
int answer = 0;
vector<int> arr(10-total,0);
for (int i = 0; i < G; i++) {
arr.push_back(GREEN);
}
for (int j = 0; j < R; j++) {
arr.push_back(RED);
}
sort(arr.begin(), arr.end());
do {
answer = max(answer, bfs(arr));
} while (next_permutation(arr.begin(), arr.end()));
cout << answer << '\n';
return 0;
}