봄버맨 2
면접 대비시간 제한2초메모리 제한512 MB
격자에서 폭탄 설치와 폭발이 반복되는 과정을 시뮬레이션하고 N초 후의 상태를 출력한다. N은 10^9까지 주어진다.
문제
봄버맨은 크기가 R×C인 직사각형 격자판에서 산다. 격자의 각 칸은 비어 있거나 폭탄이 들어 있다.
폭탄이 있는 칸은 3초가 지난 뒤 폭발하고, 폭발한 뒤에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)이면 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 폭탄이 폭발할 때 인접한 칸에 폭탄이 있으면 그 폭탄은 폭발하지 않고 파괴된다. 따라서 연쇄 반응은 일어나지 않는다.
봄버맨은 폭탄에 면역이 있어서 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다.
- 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 둔다. 모든 폭탄이 설치된 시간은 같다.
- 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
- 그다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸에 폭탄이 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
- 1초가 지난 뒤에 3초 전에 설치된 폭탄이 모두 폭발한다.
- 3과 4를 반복한다.
폭탄을 설치해 둔 초기 상태가 주어졌을 때, N초가 흐른 뒤의 격자판 상태를 구하려고 한다.
예를 들어, 초기 상태가 아래와 같은 경우를 보자.
...
.O.
...
1초가 지난 뒤에는 아무 일도 일어나지 않으므로 위와 같다고 볼 수 있다. 1초가 더 흐른 뒤 격자판의 상태는 아래와 같아진다.
OOO
OOO
OOO
1초가 지난 뒤에는 가운데에 있던 폭탄이 폭발해 가운데 칸과 인접한 네 칸이 빈 칸이 된다.
O.O
...
O.O
입력
첫째 줄에 R, C, N (1 ≤ R, C ≤ 200, 1 ≤ N ≤ 10^9)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.', 폭탄은 'O'로 주어진다.
출력
총 R개의 줄에 N초가 흐른 뒤의 격자판 상태를 출력한다.
힌트
아래는 시간이 지난 뒤 예제 격자판의 상태이다.
.......
...O...
....O..
.......
OO.....
OO.....
<초기 상태, 1초 후>
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
<2초 후>
OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO
<3초 후>
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
<4초 후>
.......
...O...
....O..
.......
OO.....
OO.....
<5초 후>