봄버맨 게임 timer 1s memory 128MB

봄버맨은 직사각형 모양의 격자 위에서 살고 있는 캐릭터이다. 이 격자의 각각의 칸은 폭탄이 있거나 아무것도 없는 둘 중 하나의 상태이다.

폭탄은 격자 위의 어떤 칸이든 설치될 수 있으며, 설치된 후 3초 후에 폭발한다. 폭탄이 폭발한다는 것은, 폭발한 위치와 이웃한 상하좌우 4칸이 아무것도 없는 상태가 된다는 뜻이다. 더 구체적으로 말해서, 폭발시 자신의 칸은 아무것도 없게 되며, 이웃한 칸에 아무것도 없으면 그대로 아무것도 없는 것이고, 폭탄이 있으면 그 폭탄은 제거된다. 여기서 “제거된” 폭탄은 폭발한 것이 아니므로, 연쇄작용을 일으키면서 그 옆의 폭탄을 또 제거시키지는 않는다.

어떤 폭발도 견딜 수 있는 봄버맨은 다음과 같은 행동을 한다. 참고로 봄버맨은 폭탄 면역이므로, 절대 죽지 않는다.

1. 봄버맨은 임의적으로 격자 위 몇 군데에 폭탄을 설치한다. 이를 초기 상태라고 한다.

2. 1초 후, 봄버맨은 아무것도 안한다.

3. 2초 후(2.로부터 1초 후), 봄버맨은 모든 폭탄이 없는 칸에 폭탄을 설치한다.

4. 3초 후(3.으로부터 1초 후), 설치된지 3초가 지난 폭탄들이 폭발한다.

5. 그 다음 짝수 초 후마다 3, 홀수 초 후마다 4를 반복한다.

매 초마다 봄버맨은 (놀랍게도) 다수의 폭탄을 동시에 설치한다.

초기 상태의 격자가 주어졌을 때, N초 후의 격자를 출력하는 프로그램을 작성하라.