백준알고리즘
미네랄
먼지의삶
2019. 10. 9. 19:11
https://www.acmicpc.net/problem/2933
2933번: 미네랄
문제 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다. 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 창영은 동굴의 왼쪽에
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
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
129
130
131
132
133
134
135
136
137
138
139
140
|
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
int r, c, n;
string map[100];
int d[100][100][100];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
vector<int> spear;
void crush(int h, int dir) {
int height = r - h;
if (dir % 2 == 0) {
for (int i = 0; i < c; i++) {
if (map[height][i] == 'x') {
map[height][i] = '.';
break;
}
}
}
else {
for (int i = c - 1; i >= 0; i--) {
if (map[height][i] == 'x') {
map[height][i] = '.';
break;
}
}
}
}
vector<pair<int, int> > cluster(int x, int y, int cnt,int io) {
queue<pair<int, int> > q;
vector<pair<int, int>> v;
q.push({ x,y });
v.push_back({ x,y });
d[x][y][io] = cnt;
bool ground = false;
while (!q.empty()) {
x = q.front().first; y = q.front().second;
q.pop();
if (!ground && x == r - 1) {
ground = true;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i]; int ny = y + dy[i];
if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
if (map[nx][ny] == 'x' && d[nx][ny][io] == 0) {
d[nx][ny][io] = cnt;
v.push_back({ nx,ny });
q.push({ nx,ny });
}
}
}
if (ground) {
v.clear();
}
return v;
}
void print() {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << map[i][j];
}cout << '\n';
}
}
void down(vector<pair<int, int>> & clu,int idx, int value) {
bool on = false;
for (int i = 0; i < clu.size(); i++) {
map[clu[i].first][clu[i].second] = '.';
}
while (true) {
for (int i = 0; i < clu.size(); i++) {
int x = clu[i].first; int y = clu[i].second;
if (x + 1 == r || (d[x + 1][y][idx] != 0 && d[x + 1][y][idx] != value))
{
//cout << x + 1 << ' ' << y << '\n';
on = true;
break;
}
}
if (on) break;
for (int j = 0; j < clu.size(); j++) {
clu[j].first = clu[j].first + 1;
//cout << "HELLO" << '\n';
}
}
for (int i = 0; i < clu.size(); i++) {
map[clu[i].first][clu[i].second] = 'x';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> r >> c;
for (int i = 0; i < r; i++) {
cin >> map[i];
}
cin >> n;
for (int i = 0; i < n; i++) {
int s;
cin >> s;
spear.push_back(s);
}
for (int i = 0; i < n; i++) {
vector<pair<int, int>> clu;
crush(spear[i], i);
int cnt = 1;
for (int j = 0; j < r; j++) {
for (int k = 0; k < c; k++) {
if (map[j][k] == 'x' && d[j][k][i] == 0) {
vector<pair<int,int> > v = cluster(j, k, cnt,i);
cnt++;
if (v.size() != 0) {
clu = v;
}
}
}
}
if (clu.size() != 0) {
int value = d[clu[0].first][clu[0].second][i];
//cout << value << " 시발!!" << '\n';
down(clu, i,value);
}
}
print();
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
BFS문제라고했는데, 사실 BFS문제라기 보다는 시뮬레이션문제에 가깝다.
군집 구하는거만 BFS로 하는거 외에는 딱히 BFS를 한게없는문제