-
-
고민
백준문제를 풀면서 가장 오래걸렸던 시물레이션 문제였다. 아마 코드 플러스에서 백준 선생님께 질문해서 받은 예제 입력과 검색을 통해서 얻은 예제 입력이 없었으면 더 오래걸렸으리라 본다. 미네랄을 부수고 공중에 떠있는 클러스터를 체크하는데 까지는 bfs로 처리했다. 이후에 클러스터 뭉치가 떨어지는 것을 처음에는 각개로 우수수 떨어진다 생각했었는데 아니였다. 클러스터 뭉치 그대로 떨어지는 것이라서 어느 부분이 제일 먼저 땅이나 미네랄에 닿는지 체크해야 했다. 이 부분에서 예제 입력 하나로 체크하려니 진행이 힘들었고, 내가 예제를 만들고자 해도 조건에 맞는 예제를 만드는 것이 어려웠다. 아래 예제는 이 분의 블로그를 참고했다.
7 7 ....... ...x... ...x... .x.x... .x.xx.. .x.xxx. xxxxxxx 5 3 4 3 1 3 10 20 ..................xx ..................x. .........xxxx...xxx. .....xx.xx.xx..xxx.. ......xxx..xx.xx.... .......x.....xxx.... .....xxx....xxx..... ...xxx...xxxx....... ...x...xxxxxx....... .xxxxxxxxx.......... 5 5 3 2 5 4 16 30 .............................. .............xxxxxxxxxxx...... .............x........x....... .............x.xxxxxx.x....... .............x..x...x.x....... .............x..x.x.x.x....... .............x..x.x.x.x....... .............x..xxxxx.x....... .............x...x....x....... .............xxxxxxxxxx....... ...xx...........x............. ..xx..........xxx............. ...xxx........x............... ....xx.......xx............... ..xxxx.......x................ .xxxxxxxxxxxxxxxxxxxxxxxxxxxx. 30 10 4 9 2 8 2 7 1 7 1 7 5 7 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 50 50 ...........................................xxxxxxx ...........................................x...... ...........................................x...... ...........................................x...... ...........................xxxxxxxxxxxxxxxxxxxx... ................xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx... ................x....................xxxx......... ...............xxx.....................x.......... ...............xxx.....................xx......... ...............xxx.....................xxxx....... ................xx.......................xx....... ................xx................................ ................x................................. ................x................................. ................x.........x...................x... .............x..xx...x...xx......xx...........x... .............x..xx...x..xxx..x....xxxx.x.x...xx... .............xx.x....x....x..xx.x.xxxx.x.x..xxx... ..........x..xxxxx...xxxxxxxx.xxx.xxx.xxxxxxxx..x. xx.......xx..xxxxxxxxx.xxxxxxxxxx.x...x.xxxxxxx.xx xx.......xx.xxxx.xxxx..xx..xxxxxxxxxx.xx.xxxxxx.xx .xxx...xxx.xxxxx.xxxxxxxx.....xx.x.xxx.xx.xxxxxxxx xxxxx..xxxxxxx.x....xxxxxx..xxxx.xx..xxxx.xxx..xxx xxxxxx..xxxxxxxx..x.x.xx.x....xxxxx.xxxxxx.x..xxx. .xxxxxx.xxxx.xx.xxx....x.xx....x..xxx..x.xxxxxxxxx ..x.xxx.xxxx.xx.xxx..xxx..x....xx.x.x.xx.xxxx.xxxx x.x.xxxxx.xxxxxxxxx.x..xx...xx.xxxx.xxx...x.xxxxx. xxxxxxxxx...x...x..xxxxxxxxxxxxxx.xxx.......xxxxx. x.x.x.xxx..x....xxxxxxxx.xx.x..xxxx...x.xxxxxxx... xxx.xxxxxx.x.xxxxxxx.xx..xxxxx.x..x.xxxxxx..x.x... xxxxxxxxxx.xxxxx.xxxxxxxxxxxxxxx.xx.x.x.xx.xx.x... xxxxxxxxxx...xxx.x.xxxxxxx.xxxxxx...xx...xxx..xx.x xx.xxx.xx.....xxxxxx.xx......xxxxxx.xx...x..xxx.xx xx..xx..x...xxxx.xx..xxxx..xxxx.xxxxxx..xxx.xxx.xx x..x.xx.xx..x.xx..x..x.xxxx.xxxx.xxxxxx..xx..xxxx. xx.xx...xxxxx.x.xxxxxxx.xxxxxxxxxxx.xxxxxxx.x.xxxx xx.xxxxxxxxxxx.xx.xx..x..xxxxx.x.xx.x..xxxx.xxxxxx xx.x.xxx..xxxx.xx..xxxxxxxxx.xxxxxxx.xxx.....xxxx. .xx.xxxxxxx.xx..xxxx.xx...xxxxxxxx.xxxxxxx.xxx..xx xx.x.xx..x..xxx...xxx.x..x.xxxxxxx.xxxxxxxxxxx.xxx xxxxx.xxxxx..xxxx.x.xx.xxx.xxx.xxxx.x.xx..xxxxxxxx x.xxx.xxxxxxxxxxxxxxxxxxxx.xxxxxxxxx....xxxxx.xxxx xx..xx.xxxxx.xxxxxx.xxxx.xxxxxxxxx.xx.x.xxxxxxxxxx xxxxxxxxx.xxxxxx.xxx.xxxxxxxxx.xxxxxx.x.xx.xxxxxx. xxxxxxxxxxxx.xxxxxx.xxxxxxxxxx..xxxxxxxxx..xxx.xxx xxxxx.xxxxxxx.xx.xx.xxxxx.xxxx.xxxxxxxxxxx..xxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxx.xxxx..xxxxxxx..xxxxxxxx xxxxxxxx.x.xxxxxxxxxxxxxxxxxxxxxxxxxxxx.xxxxxxxxxx xxxx.xxxxxxxxxxxxxxxxxxxx.xxxxxxxxxxxxxxxxxxx.xxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xx 100 21 7 37 35 39 36 38 2 32 44 37 19 29 24 25 29 43 1 32 48 26 11 44 3 6 1 13 10 48 32 8 5 6 32 16 33 32 7 34 39 10 31 8 41 35 4 13 44 30 28 20 10 29 41 1 40 20 29 5 42 33 3 37 44 7 6 10 25 6 49 40 4 33 2 6 35 39 42 40 39 7 22 33 1 1 20 20 12 3 1 48 42 7 22 8 49 9 27 10 12 -
#include <iostream> #include <string.h> #include <queue> using namespace std; int r, c; char mineral[111][111]; bool cluster[111][111]; int dx[4] = { -1, 1 , 0 , 0 }; int dy[4] = { 0, 0, -1, 1 }; int main() { ios::sync_with_stdio(false); cin >> r >> c; for (int i = 1; i <= r; i++) { for (int j = 1; j <= c; j++) { cin >> mineral[i][j]; } } int n; cin >> n; bool left = true; while (n--) { int height; cin >> height; height = r - height + 1; // del if (left == true) { for (int i = 1; i <= c; i++) { if (mineral[height][i] == 'x') { mineral[height][i] = '.'; break; } } } else { for (int i = c; i >= 1; i--) { if (mineral[height][i] == 'x') { mineral[height][i] = '.'; break; } } } left = !left; // check memset(cluster, false, sizeof(cluster)); for (int j = 1; j <= c; j++) { if (mineral[r][j] == 'x') { queue<pair<int, int> > q; q.push(make_pair(r, j)); cluster[r][j] = true; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx >= 1 && nx <= r && ny >= 1 && ny <= c) { if (!cluster[nx][ny] && mineral[nx][ny] == 'x') { cluster[nx][ny] = true; q.push(make_pair(nx, ny)); } } } } } } // down int down = r; for (int j = 1; j <= c; j++) { for (int i = r; i >= 1; i--) { if (mineral[i][j] == 'x' && cluster[i][j] == false) { int col_down = r - i; for (int k = i + 1; k <= r; k++) { if (cluster[k][j] == true) { col_down = k - i - 1; break; } } if (down > col_down) { down = col_down; } } } } for (int j = 1; j <= c; j++) { for (int i = r; i >= 1; i--) { if (i + down <= r && down != 0 && mineral[i][j] == 'x' && cluster[i][j] == false) { mineral[i + down][j] = mineral[i][j]; mineral[i][j] = '.'; } } } } for (int i = 1; i <= r; i++) { for (int j = 1; j <= c; j++) { cout << mineral[i][j]; } cout << '\n'; } return 0; }
Home