2933번: 미네랄
문제 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다. 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 창영은 동굴의 왼쪽에
www.acmicpc.net
/* 1시간 32분 소요 */
/* 1. map indexing 오류 : 바닥은 0이 아니라 R - 1 */
/* 2. DFS 실행 조건 누락 */
/* 3. 몇 칸 내릴 수 있는지 제대로 세기 위해서는 먼저 내릴 클러스터를 map에서 지워야 한다. */
#include <iostream>
#include <string.h>
#include <vector>
#define loop(x, n) for(int x = 0; x < (n); ++x)
using namespace std;
int R, C, N;
char map[100][100];
int dr[] = { 1, 0, 0, -1 };
int dc[] = { 0, 1, -1, 0 };
#define IN(r, c) (0 <= (r) && (r) < R && 0 <= (c) && (c) < C)
bool lv, v[100][100]; vector<pair<int, int>> cl;
void DFS(int r, int c) {
if (r == R - 1) /* 1 */
lv = 0;
v[r][c] = 1;
cl.emplace_back(r, c);
loop(d, 4) {
int cr = r + dr[d], cc = c + dc[d];
if (IN(cr, cc) && !v[cr][cc] && map[cr][cc] == 'x')
DFS(cr, cc);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> R >> C;
loop(r, R) loop(c, C) cin >> map[r][c];
cin >> N;
loop(n, N) {
int r; cin >> r; r = R - r;
int c;
if (n % 2) { // 오른쪽 -> 왼쪽
for (c = C - 1; c >= 0; --c)
if (map[r][c] == 'x')
break;
if (c == -1) continue;
}
else {
for(c = 0; c < C; ++c)
if (map[r][c] == 'x')
break;
if (c == C) continue;
}
map[r][c] = '.';
loop(d, 4) {
int nr = r + dr[d], nc = c + dc[d];
if (!IN(nr, nc) || map[nr][nc] != 'x') /* 2 */
continue;
lv = 1; loop(r, R) memset(v[r], 0, C); cl.clear();
DFS(nr, nc);
if (lv == 0) continue;
for (auto p : cl) map[p.first][p.second] = '.'; /* 3 */
int dr;
for(dr = 1; ; ++dr)
for(auto p : cl)
if (p.first + dr == R || map[p.first + dr][p.second] == 'x') {
--dr; goto out;
}
out:
for (auto p : cl) map[p.first + dr][p.second] = 'x';
}
}
loop(r, R) {
loop(c, C)
cout << map[r][c];
cout << '\n';
}
return 0;
}