[アルゴリズム解析]BOJ 20056法師サメと火球

今日の質問はBOJ 20056魔法使いサメと火球です.これはシミュレーションの問題で、私は難しいと思います.私はシミュレーションに弱いようです.

BOJ 20056魔法使いサメと火球

サメは魔法使いになり、火球を覚えた.
ガイドサメの大きさはN×N人グリッドはM個の火の玉を発射した.最初は、火の玉はそれぞれの位置で待機して移動します.i番火の玉の位置は(ri,ci)、質量はmi、方向はdi、速度はsiです.位置(r,c)は、r行c列を表す.
グリッドの行と列は1からN番号、1行はN番号、1列はN番号に関連付けられます.
火の玉の方向は、あるセルに隣接する8つのセルの方向を意味し、整数は次のとおりです.

魔法使いのサメがすべての火球を移動させると、次のようなことが起こります.

すべての火球が自分の方向diに移動する速度はsi格である.

の移動では、同じ車両に複数の火の玉がある可能性があります.

移動がすべて終了すると、火の玉が2つ以上ある格子で次のようなことが起こります.

同じ格子の火球が一つになっています.

火球は4つの火球に分かれている.

に分けられた火の玉の質量、速度、方向は以下の通りである.
質量は火球質量の和である.

24172速度は、火の玉の速度の和/火の玉の数の和である.

が合わさった火の玉の方向が奇数または偶数の場合、方向は0、2、4、6であり、そうでなければ1、3、5、7である.

質量がゼロの火の玉が消えます.

ガイドサメはK回移動を命令した後,残りの火球質量の和を求める.

にゅうしゅつりょく

[入力]
1行目はN MK
2行目から、M行ごとにFire Ballの情報が与えられます.火球の情報は5つの整数ri,ci,mi,si,diからなる.
2つの異なる火球の位置が同じである場合、入力は与えられません.
[出力]
法師サメはK回移動を命じた後、残りの火球質量の和を出力する.
[制限]

4 ≤ N ≤ 50

0 ≤ M ≤ N2

1 ≤ K ≤ 1,000

1 ≤ ri, ci ≤ N

1 ≤ mi ≤ 1,000

1 ≤ si ≤ 1,000

0 ≤ di ≤ 7

私の答え

私は問題を見ると容易ではないと思います.
特殊なアルゴリズムを用いた問題に比べて,このように複数の要素の問題を注意深く確認し,正しく処理することはより困難であるようである.
まず、問題は大きく二つの段階に分けられる.
移動火球+マージ火球再分割
また、この問題の特徴は火球に多くの要素があることです.火球の位置を表す座標と質量、速度、移動方向を覚えておいてください.私の場合、質量、速度、移動方向がpropertyの構造体FireBallを宣言し、N*Nの大きさの座標をベクトルとする2次元配列FireBallを管理する.
このような資料構造を宣言する方法が有効かどうか疑問だが、入力範囲が大きくないため、簡単で正確な解答方式を選んだ.

移動

回転二次元配列mapは、その位置する球速度、移動方向を用いて新しい座標に移動し、移動後の球を記録する新しい二次元座標mapに反映される.
新しい座標を求める過程で苦労したが,移動速度がNより大きい場合,mod演算によりその値を小さくし,移動方向が境界を超え,移動後の座標値が0より小さいかN−1より大きい場合,処理の部分が重要である.

マージ後に再分割

移動した球の二次元配列movedを保存して同じ探索を行った.
このとき、座標中のボールが1つしかない場合は、合わせて分けて再反映したmovedのうち、2つ以上のボールのみが行われる.
位置上のボールの質量と速度とを求め、移動方向が一致しているかどうかを確認した後、新しい質量、速度、移動方向を反映してmapに入れる.
このプロセスはK回行われ、最後の実行であれば、最終的にmapに入ったボールの質量を合わせて返します.
ループの座標部分の練習が必要みたい…!

コード#コード#

#include <iostream>
#include <vector>

// boj 20056 마법사 상어아 파이어볼, 골드 5, simulation
using namespace std;

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

typedef struct fireball {
    int mass;
    int speed;
    int dir;

    fireball(int m, int s, int d) {
        this->mass = m;
        this->speed = s;
        this->dir = d;
    }
}FireBall;

vector<vector<vector<FireBall>>> map;

int moveFireBall(int N, int M, int K){
    int left_mass = 0;
    int order = K;

    while (order>0){
        order--;
        vector<vector<vector<FireBall>>> moved(N+1, vector<vector<FireBall>>(N+1));

        // 1. 이동
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (map[i][j].empty()) continue;

                for (int k = 0; k < map[i][j].size(); ++k){
                    int m = map[i][j][k].mass;
                    int s = map[i][j][k].speed;
                    int d = map[i][j][k].dir;

                    int nr = i + dy[d] * (s % N);
                    if (nr<1) nr += N;
                    if (nr>N) nr -= N;

                    int nc = j + dx[d] * (s % N);
                    if(nc<1) nc += N;
                    if (nc>N) nc -= N;

                    moved[nr][nc].push_back(FireBall(m, s, d));
                }
            }
        }

        // 2. 정리
        map.clear();
        map.assign(N+1, vector<vector<FireBall>>(N+1));

        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (moved[i][j].empty()) continue;

                if (moved[i][j].size()==1){
                    map[i][j].push_back(FireBall(moved[i][j][0].mass,moved[i][j][0].speed,moved[i][j][0].dir));
                    if(order==0) left_mass += moved[i][j][0].mass;
                    continue;
                }

                int mass_sum = 0, speed_sum = 0;
                bool same_dir = true;

                for (int k = 0; k < moved[i][j].size(); ++k) {
                    mass_sum += moved[i][j][k].mass;
                    speed_sum += moved[i][j][k].speed;

                    if(k>0 && same_dir){
                        if (moved[i][j][k-1].dir%2 != moved[i][j][k].dir%2) same_dir = false;
                    }

                }

                mass_sum = mass_sum/5;
                if (mass_sum == 0) continue;

                speed_sum = speed_sum/moved[i][j].size();

                int dir_base = -1;
                if (same_dir) dir_base = 0;
                else dir_base = 1;

                for (int k = 0; k <=6 ; k += 2) {
                    map[i][j].push_back(FireBall(mass_sum, speed_sum, dir_base+k));
                    if (order==0) left_mass += mass_sum;
                }
            }
        }

    }

    return left_mass;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N, M, K;
    cin>>N>>M>>K;

    map.assign(N+1, vector<vector<FireBall>>(N+1));

    int r, c, m, s, d;
    for (int i = 0; i < M; ++i) {
        cin>>r>>c>>m>>s>>d;
        map[r][c].push_back(FireBall(m, s, d));
    }

    cout<<moveFireBall(N,M,K);

    return 0;
}