[解析アルゴリズム解答]BOJ 21610法師サメとヒマワリ

11月の初日!
いろんな面から再開する気持ちで、
今日NAVER漫画の面接淘汰のメールを受け取って、1ヶ月近く待って落ちて、しかし本当に落ちて、本当にとても悲しんで、ほほほ、
下半期はまだ完全に終わっていないので、今日から1つのアルゴリズムだけを勉強して、比較的油断しているCSとiOSを主とするプロセス学習をします.
今日の問題はBOJ 21610法師サメとひまわり題です.やはり私の模擬問題が弱いのでやってみましたが、前回と似たような問題をするより進歩しました!

BOJ 21610法師サメとひまわり

魔法使いサメは火球、竜巻、吹雪、水放射バーグ魔法を使うことができます.今日新しく学んだ魔法はバーバラです.ひまわりが咲くと、空は雨雲になる.今日は雨の大きさをN×私はN人格で練習します.格子の各格子にはかごがあり、かごが格子全体を占めています.かごに貯まる水量に制限はありません.(r,c)はメッシュのr行c列のバスケットを表し,A[r][c]は(r,c)のバスケットに格納された水量を表す.
メッシュの最左上は(1,1),最右下は(N,N)である.練習のため、ガイドサメは1番行とN番行をつなぎ、1番列とN番列もつなぎました.つまり、N番行の下は1番行、1番行の上はN番行、1番列の左側はN番列、N番列の右側は1番列となる.
ヒマワリ(N,1),(N,2),(N−1,1),(N−1,2)を施すと雨雲が発生する.雲が格子全体を占めている.M号を雲に移動するように命令します.i移動コマンドは、方向diと距離siからなる.方向は全部で8方向で、8つの整数で表されます.1最初は順番←,↖,↑,∧,→,繰り返し,↓,͜.コマンドが移動する場合は、次の順序で行います.

すべての雲がdi方向にsi格子を移動します.

各雲で降雨し,雲間のかごに貯蔵された水量は1増加した.

雲はすべて消えた.

2では、増加した格(r,c)に水放射バーグ魔法を施す.逆水エラー魔法を使用すると、対角線方向距離が1の格子に水が入ったバスケットの数(r,c)でバスケットの数が増加します.

の場合、移動とは異なり、境界を越えたセルは対角線方向距離が1のセルではありません.

例えば、(N,2)において、隣接する対角線セルは(N−1,1)、(N−1,3)であり、(N,N)において、隣接する対角線セルは(N−1,N−1)のみである.

かごに貯蔵されている水量が2を超えるすべての格子に雲が発生し、水量が2減少します.このとき雲が発生する格子は3で雲が消える格子ではない.

M回移動した後、かごの中の水量の和を求めます.

にゅうしゅつりょく

[入力]
1行目はN,Mです.
2行目からN行にはN個の整数がある.r 1行目のc個の整数はA[r][c]を表す.
次のM行では、移動する情報di,siが順に1行ずつ1行ずつとなる.
[出力]
1行目のM回移動が全て終了した後、かごの中の水量の和を出力します.
[制限]

2 ≤ N ≤ 50

1 ≤ M ≤ 100

0 ≤ A[r][c] ≤ 100

1 ≤ di ≤ 8

1 ≤ si ≤ 50

私の答え

特別な方法というよりは、必要条件をよく確認して実行すればいいのです.簡単そうで間違いやすい問題ですが、私はこのタイプに弱いです.
問題の解決は、クラウドの移動->水エラー魔法のコピー->新しいクラウドの作成の3つの段階に分けられます.

雲の移動

まずクラウドを移動します.私はすべての座標をチェックするたびにプロセスが好きではないので、以前の雲の位置をvector<pair<int,int>> cloud配列に保存します.
M回移動で移動方向と速度が与えられるが,この方向と速度から出雲移動の新しい座標を求める過程に注意する.
制限条件から,si値は最高50に達し,nをはるかに超えることができる.1行がN行、1列がN列に関連付けられているため、si値は最終的にmod演算を適用したsi%N値と同じであることを覚えておいてください.
mod演算されたsi値と同様にdi方向に移動するセル数は、2つの変数row_moveおよびcol_moveにそれぞれ格納され、現在位置cloud[i]にはそれぞれ2つの値が加算され、演算されてメッシュ内でループされる.
私は数学の上で規則の特別な妙策を探すことを知らないで、私はただ情況によって描いて、それからその演算を見つけて、row_move、col_moveの値の座標をプラスしてメッシュの位置から外れるので、まずrow_move、col_moveにそれぞれNをプラスします.前の座標にmod演算を加えると,ループメッシュ内の正しい移動位置を求めることができる.
このようにして新しい雲の位置を求め,配列new_cloudに格納し,雲の位置のかごに水1を加える.また、N*Nに配列されたisCloudには、新しい雲の位置が記録されている.

水コピーエラー

水のコピーエラーは簡単です.new_cloudの新しい雲の位置から、対角線方向の1つの格子に水が存在するバスケットの数を計算し、それに応じてその格子のバスケットの数を増加させる.対角線方向なので、合計8方向のうち奇数index万を選択し、メッシュ境界内のセルを確認するだけです.

新しいクラウドの作成

その後、雲移動時に新雲位置をチェックするN*Nサイズのメッシュ配列isCloudにより、雲の位置ではないバスケット内の水の量が2より大きくなると、2行分の水の量が減少し、その位置で新たな雲が生成される.
新しいクラウドの位置は、次回の移動時に使用するために、以前使用していた配列cloudをリセットして追加します.

コード#コード#

#include <iostream>
#include <vector>

// boj 21610 마법사 상어와 비바라기, 시뮬레이션, 골드 5
using namespace std;

int N, M;

vector<vector<int>> map;
vector<pair<int, int>> moving;

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

int moveCloud(){
    int left = 0;
    int order = 0;
    vector<pair<int, int>> cloud;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i>=N-2 && i<= N-1 && j>=0 && j<=1) {
                cloud.push_back({i, j});
            };
        }
    }

    while (order<M){
        // 구름 이동, 비 1씩 내림
        int dir = moving[order].first-1, speed = moving[order].second;
        vector<pair<int, int>> new_cloud;
        int row_move = dy[dir] * (speed%N);
        int col_move = dx[dir] * (speed%N);

        vector<vector<bool>> isCloud(N, vector<bool>(N, false));
        for (int i = 0; i < cloud.size(); ++i) {
            int nr = (cloud[i].first + row_move+N) % N;
            int nc = (cloud[i].second + col_move+N) % N;

            map[nr][nc] += 1;
            isCloud[nr][nc] = true;
            new_cloud.push_back({nr, nc});
        }

        // 물복사버그
        for (int i = 0; i < new_cloud.size(); ++i) {
            int count = 0;
            for (int j = 1; j <8 ; j+=2) {
                int nr = new_cloud[i].first + dy[j];
                int nc = new_cloud[i].second + dx[j];

                if (nr<0 || nr>=N || nc<0 || nc>=N) continue;
                if (map[nr][nc]>0) count++;
            }
            map[new_cloud[i].first][new_cloud[i].second] += count;
        }
        new_cloud.clear();
        cloud.clear();

        // 새로운 구름 생성하기 
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (!isCloud[i][j] && map[i][j]>=2){
                    cloud.push_back({i,j});
                    map[i][j] -= 2;
                }
                if (order==M-1) left += map[i][j];
            }
        }

        order++;
    }

    return left;
}


int main() {
    cin>>N>>M;

    map.assign(N, vector<int>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin>>map[i][j];
        }
    }

    moving.assign(M,{0,0});
    for (int i = 0; i < M; ++i) {
        cin>>moving[i].first>>moving[i].second;
    }

    int answer = moveCloud();
    cout<<answer;

    return 0;
}