봄버맨
면접 대비시간 제한2초메모리 제한512 MB
격자에서 폭탄을 놓고 3초 뒤 폭발하는 규칙을 반복해 N초 후의 상태를 출력한다.
문제
봄버맨은 크기가 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, N ≤ 200)이 주어진다. 둘째 줄부터 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초 후>