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
117
118
119
120
121
122
123
124
125
126
127
128
| #include <iostream>
#include <cstring>
#include <vector>
#include <list>
#include <algorithm>
#define MAX_WIDTH 50
#define WALL 1
using namespace std;
int map[MAX_WIDTH][MAX_WIDTH];
typedef struct Virus {
int row;
int col;
int time;
bool operator < (Virus v) {
if (map[row][col] == 2 && map[v.row][v.col] != 2)
return false;
else if (map[row][col] != 2 && map[v.row][v.col] == 2)
return true;
else
return time > v.time;
}
} Virus;
int width, numOfActiveVirus, numOfVirus;
vector<Virus> virus;
bool canSpread = false;
int minToSpreadVirus(vector<Virus> active, int deep);
int min(int a, int b);
int main() {
cin >> width >> numOfActiveVirus;
numOfVirus = 0;
for (int i = 0; i < width; i++) {
for (int j = 0; j < width; j++) {
cin >> map[i][j];
if (map[i][j] == 2) {
virus.push_back({ i, j, 0});
numOfVirus++;
}
}
}
vector<Virus> temp;
int result = minToSpreadVirus(temp, 0);
if (result == -1 && canSpread)
cout << 0;
else
cout << minToSpreadVirus(temp, 0);
}
int minToSpreadVirus(vector<Virus> active, int deep) {
if (active.size() == numOfActiveVirus) {
//퍼트리기
list<Virus> q;
bool visit[MAX_WIDTH][MAX_WIDTH] = { 0, };
for (int i = 0; i < active.size(); i++) {
q.push_back(active[i]);
visit[active[i].row][active[i].col] = true;
}
vector<Virus> minTimeCandidate;
while (!q.empty()) {
Virus v = q.front();
q.pop_front();
int count = 0;
if (v.row > 0 && !visit[v.row - 1][v.col] && map[v.row - 1][v.col] != 1) {
q.push_back({ v.row - 1, v.col, v.time + 1 });
visit[v.row - 1][v.col] = true;
if(map[v.row-1][v.col] == 0)
count++;
}
if (v.col < width - 1 && !visit[v.row][v.col + 1] && map[v.row][v.col + 1] != 1) {
q.push_back({ v.row, v.col + 1, v.time + 1 });
visit[v.row][v.col + 1] = true;
if(map[v.row][v.col+1] == 0)
count++;
}
if (v.row < width - 1 && !visit[v.row + 1][v.col] && map[v.row + 1][v.col] != 1) {
q.push_back({ v.row + 1, v.col, v.time + 1 });
visit[v.row + 1][v.col] = true;
if(map[v.row+1][v.col]==0)
count++;
}
if (v.col > 0 && !visit[v.row][v.col - 1] && map[v.row][v.col - 1] != 1) {
q.push_back({ v.row, v.col - 1, v.time + 1 });
visit[v.row][v.col - 1] = true;
if(map[v.row][v.col-1] == 0)
count++;
}
if (count == 0)
minTimeCandidate.push_back(v);
}
for (int i = 0; i < width; i++)
for (int j = 0; j < width; j++)
if (!visit[i][j] && map[i][j] != 1)
return -1;
canSpread = true;
sort(minTimeCandidate.begin(), minTimeCandidate.end());
if (map[minTimeCandidate[0].row][minTimeCandidate[0].col] == 2)
return -1;
else
return minTimeCandidate[0].time;
}
if (numOfVirus - deep < numOfActiveVirus - active.size())
return -1;
int a = minToSpreadVirus(active, deep + 1);
active.push_back(virus[deep]);
int b = minToSpreadVirus(active, deep + 1);
return min(a, b);
}
int min(int a, int b) {
if (a == -1)
return b;
else if (b == -1)
return a;
else
return a < b ? a : b;
}
|
