[アルゴリズム解解析]BOJ 16918春スーパーマン

今日の質問はBOJ 16918春スーパーマンです!

BOJ 16918春スーパーマン

春スーパーマンの大きさはR×C人の矩形の格子板に住んでいます.グリッドの各格子は空か爆弾が入っています.
爆弾のある部屋は3秒後に爆発し、爆弾が爆発した後、爆弾のある部屋は空室に破壊され、隣接する4部屋も一緒に破壊された.すなわち,爆弾が存在する部屋が(i,j),(i+1,j),(i−1,j),(i,j+1),(i,j−1)であれば,(i,j−1)も共に破壊される.爆弾が爆発すると、隣の部屋に爆弾があり、隣の爆弾は爆発せずに破壊されます.そのため、連鎖反応はなかった.
春にバーマンは爆弾に免疫力があり、グリルの上のすべての格子を自由に移動することができる.春のバーマンは以下のように表現されています.

の最初の春、バーマンはいくつかの車両に爆弾を設置した.すべての爆弾が取り付けられた時間は同じです.

次の一秒で、春バーマンは何もしません.

から1秒以内に、爆弾が設置されていないすべての部屋に爆弾を設置します.つまり、すべての車両に爆弾があるということです.爆弾はすべて同時に取り付けられたと仮定します.

1秒後、3秒前に取り付けられた爆弾はすべて爆発した.

3と4を繰り返します.
爆弾の初期状態を設定すると、N秒後のグリッド状態を求めようとする.

たとえば、初期状態が次の場合です.

...
.O.
...

一秒たっても何も起こらないので、このように言えます.あと1秒でメッシュボードの状態は次のようになります.

OOO
OOO
OOO

1秒後、真ん中の爆弾が爆発し、真ん中の格子と隣の格子がスペースになった.

O.O
...
O.O

にゅうしゅつりょく

[入力]
第1行は、R、C、N(1≦R、C、N≦200)を与える.2行目から、R行はメッシュプレートの初期状態を与える.スペースは「.」ロ、爆弾は「O」で与えられる.
[出力]
共R行、N秒後のメッシュボード状態を出力します.

私の答え

これはグラフ探索問題で探した問題であるが,解の際にdfsがなく,bfsも簡単に解くことができることが分かった.シミュレーションみたいな感じで、、、、?
1秒から、毎秒規則に従ってグリッドプレートの状態を変更すればよい.爆弾は設置3秒後に爆発したため、各爆弾の設置時間を管理するために2次元配列installTimeが確立された.
爆弾を1つ取り付けるたびに、その時点を記録し、1つの時点を変更するたびに、3秒後に爆弾を爆発させ、installTimeの値を初期化します.

コード#コード#

#include <iostream>
#include <vector>

using namespace std;

vector<vector<char>> matrix;
vector<vector<int>> installTime;

int dy[5] = {0,-1,0,1,0};
int dx[5] = {0,0,1,0,-1};

void installBomb(int R, int C, int sec){
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j){
            if (matrix[i][j]=='.') {
                matrix[i][j] = 'O';
                installTime[i][j] = sec;
            }
        }
    }
}

void removeBomb(int R, int C, vector<pair<int, int>> points){
    for (int i = 0; i < points.size(); ++i) {
        for (int k = 0; k < 5; ++k) {
            int row = points[i].first+dy[k], col = points[i].second+dx[k];
            if (row<0||row>=R||col<0||col>=C) continue;
            matrix[row][col] = '.';
            installTime[row][col] = -1;
        }
    }
}

void moveMan(int R, int C, int N){
    int sec = 1;

    while (sec<N){
        sec++;
        installBomb(R, C, sec);

        if (sec==N) break;

        sec++;
        vector<pair<int, int>> remove_points;
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j){
                if (sec-installTime[i][j]==3){
                    remove_points.push_back({i,j});
                }
            }
        }

        removeBomb(R, C, remove_points);
    }
}

int main() {
    int R, C, N;
    cin>>R>>C>>N;

    matrix.assign(R, vector<char>(C, ' '));
    installTime.assign(R, vector<int>(C, -1));
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin>>matrix[i][j];
            if (matrix[i][j] =='O') installTime[i][j] = 0;
        }
    }

    moveMan(R, C, N);

    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j){
            cout<<matrix[i][j];
        }
        cout<<'\n';
    }


    return 0;

}