백준 16918번 : 봄버맨 (c++)

https://www.acmicpc.net/problem/16918

16918번: 봄버맨

문제

봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다.

폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다.

봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다.

• 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.

• 다음 1초 동안 봄버맨은 아무것도 하지 않는다.

• 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.

• 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.

• 3과 4를 반복한다.

폭탄을 설치해놓은 초기 상태가 주어졌을 때, N초가 흐른 후의 격자판 상태를 구하려고 한다.

입력
첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

출력
총 R개의 줄에 N초가 지난 후의 격자판 상태를 출력한다.

예제 입력
6 7 3
.......
...O...
....O..
.......
OO.....
OO.....

예제 출력
OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

#include <iostream>
#include <cstring>
using namespace std;

int R,C,N;
int time;
int map[200][200];
int dy[]={-1,0,1,0,0};
int dx[]={0,1,0,-1,0};
bool chk[200][200];

void simulation(){
    if(time==N) return;
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            if(map[i][j]==0){
                map[i][j]=3;
            }
        }
    }
    time++;
    if(time==N) return;
    while(1){
        
        memset(chk,false,sizeof(chk));
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(map[i][j]>0){
                    map[i][j]--;
                }
            }
        }
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(map[i][j]==1){
                    for(int k=0;k<5;k++){
                        int ny = i+dy[k];
                        int nx = j+dx[k];
                        if(ny<0||nx<0||ny>=R||nx>=C)    continue;
                        chk[ny][nx]=true;
                    }
                }
            }
        }
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(chk[i][j]){
                    map[i][j]=0;
                }
            }
        }
        time++;
        if(time==N) return;
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(map[i][j]==0){
                    map[i][j]=3;
                }
            }
        }
        time++;
        if(time==N) return;
    }
}


int main(){

    freopen("input.txt","r",stdin);

    cin>>R>>C>>N;

    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            char a;
            cin>>a;
            if(a=='O'){
                map[i][j]=2;
            }
        }
    }
    time++;
    simulation();

    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            if(map[i][j]!=0){
                cout<<"O";
            }else{
                cout<<".";
            }
        }
        cout<<"\n";
    }
    return 0;
}