미네랄 2
https://www.acmicpc.net/problem/18500
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 2109 | 713 | 549 | 34.355% |
문제
창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다.
두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유 인지를 결정하기로 했다.
싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.
동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다.
각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.
창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다.
막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.
막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.
미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다.
새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다.
떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 계속해서 떨어진다.
클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.
동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다.
모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)
다음 R개 줄에는 C개의 문자가 주어지며, ‘.’는 빈 칸, ‘x’는 미네랄을 나타낸다.
다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)
마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다.
모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다.
첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.
공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다.
클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.
(2933번 문제와 차이)
출력
입력 형식과 같은 형식으로 미네랄 모양을 출력한다.
예제 입력 1
5 6 ...... ..xx.. ..x... ..xx.. .xxxx. 1 3
예제 출력 1
...... ...... ..xx.. ..xx.. .xxxx.
예제 입력 2
8 8 ........ ........ ...x.xx. ...xxx.. ..xxx... ..x.xxx. ..x...x. .xxx..x. 5 6 6 4 3 1
예제 출력 2
........ ........ ........ ........ .....x.. ..xxxx.. ..xxx.x. ..xxxxx.
예제 입력 3
7 6 ...... ...... xx.... .xx... ..xx.. ...xx. ....x. 2 6 4
예제 출력 3
...... ...... ...... ...... ..xx.. xx.xx. .x..x.
예제 입력 A
13 100 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ..................................................x................................................x ..................................................x................................................x ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. 11 1 1 1 1 1 1 1 1 1 1 1
예제 출력 A
.................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ..................................................x................................................x ...................................................................................................x
예제 입력 B
9 8 ........ ...xxx.. .xxx.... .x.x.xxx .x.x...x .x.xxx.x .x.....x .x.....x .xxx...x 1 7
예제 출력 B
........ ........ ...xxx.. .xxx.xxx .x.x...x .x.x...x .x.xxx.x .x.....x .xxx...x
예제 입력 C
4 4 xxxx xx.x x..x ...x 1 3
예제 출력 C
xxxx .x.x ...x x..x
예제 입력 D
7 5 ..... .xxx. .x... xx.xx x...x x...x x...x 1 4
예제 출력 D
..... ..... .xxx. .x.xx xx..x x...x x...x
예제 입력 E
2 2 .. .x 1 2
예제 출력 E
.. .x
예제 입력 F
5 5 xxxxx x.... xxxxx x.... x.... 10 1 2 3 4 5 1 2 3 4 5
예제 출력 F
..... ..... ..... .xxxx xxxx.
예제 입력 G
10 10 xxxxxxxxxx ....x..... ...xxx.... .....x.... ....xx.... .....x.... xxxxxx.... ..x....... .xxxx..... ...xxxxxxx 10 9 8 7 6 5 4 3 2 1 1
예제 출력 G
.......... .......... .......... .......... .......... .......... xxxxxxxxxx ....xx.... xxxxxx.... .xxxxxxxx.
예제 입력 H
4 4 ...x ..xx .xxx xxxx 10 1 2 3 4 1 2 3 4 3 4
예제 출력 H
.... .... .xxx ..xx
예제 입력 I
10 20 ..xxxxxxxxxxxxxxx... ..x.............x... ..x.............x... ..x.............x... ..x.............x... ..x.............x... ..x.............x... ..xxxxxx........x... ................x... x...............x... 2 1 7
예제 출력 I
.................... ..xxxxxxxxxxxxxxx... ..x.............x... ..x.............x... ..x.............x... ..x.............x... ..x.............x... ..x.............x... ..xxxxxx........x... ................x...
예제 입력 J
9 8 ........ .xxxx... .x...... .x.xxxx. .x....x. .x....x. .xxxx.x. ....xxx. ......x. 1 2
예제 출력 J
........ ........ .xxxx... .x.xxxx. .x....x. .x....x. .x....x. .xxxxxx. ......x.
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2009 > Croatian Regional Competition in Informatics 2009 5번
Olympiad > Croatian Highschool Competitions in Informatics > 2009 > Regional Competition – Juniors 4번
- 데이터를 추가한 사람: heize
알고리즘 분류
통과된 코드
나는 2933번을 해결할 때 공중에 있는 미네랄 리스트의 하단부를 전부 확인하는 방법으로 구현해서 다른 것이 없다.
골드 2 문제를 해결하니 골드 1을 같이 주네?? 개꿀
#include <iostream> #include <list> #include <queue> using namespace std; // RC의 범위 최대값 constexpr int MAX = 101; // 기본 맵 char map[MAX][MAX]; // 방문처리 bool mapCheck[MAX][MAX]; // BFS 사용할 Q queue<pair<int, int>> myQ; pair<int, int> tempP; // R 행, C 열, N 막대기를 던진 횟수 int R, C, N; int dx, dy, dis; int temp = 0; // 탐색하는 방향 설정 => 상, 하 ,좌 ,우 int dxdy[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; list<int> myList; list<int>::iterator it; list<pair<int, int>> cList; list<pair<int, int>>::iterator cit; // true = left, false = right bool check = false, leftRight = false; void BFS(int x, int y) { myQ.push(make_pair(x, y)); while (!myQ.empty()) { tempP = myQ.front(); myQ.pop(); for (int i = 0; i < 4; i++) { dy = tempP.second + dxdy[i][1]; dx = tempP.first + dxdy[i][0]; // 문제의 범위를 벗어나는 경우 => 넘어간다. if (dx <= 0 || dy <= 0 || dy > C || dx > R) continue; // 방문 처리가 되었거나 빈공간 => 넘어간다. if (mapCheck[dx][dy] == true || map[dx][dy] == '.') continue; mapCheck[dx][dy] = true; myQ.push(make_pair(dx, dy)); } } } void CheckFloor() // 바닥을 체크합니다. { for (int y = 1; y <= C; y++) { // 바닥에 클러스터가 발견되고 방문처리가 되지 않았다면 if (map[1][y] == 'x' && mapCheck[1][y] == false) { BFS(1, y); // BFS로 마킹 } } } int main() { ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화 // cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다. cin.tie(NULL); cout.tie(NULL); // 처음 맵을 초기화 해준다. for (int x = 1; x < MAX; x++) { for (int y = 1; y < MAX; y++) { map[x][y] = '.'; } } cin >> R >> C; // 미네랄의 위치를 설정 (아래서 부터 시작) for (int x = R; x >= 1; x--) { for (int y = 1; y <= C; y++) { cin >> map[x][y]; } } cin >> N; /// 던진 횟수와 높이를 설정 while (N > 0) { cin >> temp; myList.push_back(temp); N--; } // 던진 막대기 리스트를 순회합니다. for (it = myList.begin(); it != myList.end(); it++) { check = false; // 미네랄 부셔짐 체크 해제 cList.clear(); // 공중의 미네랄 리스트 초기화 // 해당 위치에 미네랄이 있는지 검색합니다. if (leftRight) { // 좌측 검색 for (int y = C; y >= 1; y--) { // 만약 미네랄이 있다면 if (map[*it][y] == 'x') { // 해당 미네랄을 빈 공간으로 만든다. map[*it][y] = '.'; // 바닥과 연결된 모든 클러스터를 방문처리 CheckFloor(); check = true; break; } } leftRight = !leftRight; } else { // 우측 검색 for (int y = 1; y <= C; y++) { // 만약 미네랄이 있다면 if (map[*it][y] == 'x') { // 해당 미네랄을 빈 공간으로 만든다. map[*it][y] = '.'; // 바닥과 연결된 모든 클러스터를 방문처리 CheckFloor(); check = true; break; } } leftRight = !leftRight; } if (check) { // 미네랄이 부셔졌다면 // 공중에 있는 클러스트들을 리스트에 담는다. for (int x = R; x >= 1; x--) { for (int y = C; y >= 1; y--) { if (map[x][y] == 'x' && mapCheck[x][y] == false) { cList.push_back(make_pair(x, y)); } } } // 공중에 미네랄이 바닥과 연결될때까지 반복 dis = 1; bool floor = true; while (floor) { if (cList.size() == 0) break; for (cit = cList.begin(); cit != cList.end(); cit++) { tempP.first = cit->first; tempP.second = cit->second; if (mapCheck[tempP.first - (dis + 1)][tempP.second] == true || tempP.first - (dis + 1) == 0) { floor = false; break; } } dis++; } if (!floor) { for (cit = cList.begin(); cit != cList.end(); cit++) { tempP.first = cit->first; tempP.second = cit->second; map[tempP.first][tempP.second] = '.'; } for (cit = cList.begin(); cit != cList.end(); cit++) { tempP.first = cit->first; tempP.second = cit->second; map[tempP.first - (dis - 1)][tempP.second] = 'x'; } } // 방문 처리를 초기화 for (int x = R; x >= 1; x--) { for (int y = 1; y <= C; y++) { mapCheck[x][y] = false; } } } } for (int x = R; x >= 1; x--) { for (int y = 1; y <= C; y++) { cout << map[x][y]; } if (x == 1) break; cout << "\n"; } return 0; }