[BOJ]20165-我慢のドミノ骨牌職人胡石

💎 質問する

人を怒らせる方法はいろいろあります.その中で最悪なのは、努力して立てたドミノの骨牌を倒すことだ.これを利用して、二人で攻撃と守備を行うゲームだ.攻撃隊員はドミノの骨牌を倒し続け、守備員はドミノの骨牌を作り続けたいと思っている.本ゲームは以下のように行います.

N行M列の2次元メッシュ状ゲームボードの各メッシュにドミノ骨牌を作成する.ドミノの骨牌ごとに1つまたは5つ以下の高さがあります.

グランドスラムはフォワードが先に攻撃し、バックは攻撃終了後に守備する.

フォワードは特定の格子に置かれたドミノの骨牌を東、西、南、北の任意の方向に倒す.長さKのドミノがある方向に転倒すると、その方向K-1のドミノのうちまだ転倒していないものが同じ方向に次々と転倒する.この場合、ドミノの特性上、ドミノが連続して転倒する可能性がある.転んだドミノの骨牌がある格子を攻撃すれば、何も起こらない.

バックは転倒したドミノの骨牌に欲しいものを新たに立てることができる.転んでいないドミノの骨牌を作りたいなら、何も起こらない.

R回で3、4回の過程を繰り返す.攻撃手がそのターンに転倒したドミノの数をラウンドごとに数え、Rターンの合計が攻撃手の点数となる.

ドミノの骨牌攻撃の例図です.図の赤い数字は転んだドミノの骨牌を表している.
例えば、{3、1、2、2、2}の高いドミノの骨牌が一列に並んでいて、3番を右側に押すと左側の3つが右に転びます.そのため、新しく転倒したドミノのチェーン作用が起こり、その過程で4位の長さ2のドミノも転倒する.そして、最後にドミノの骨牌も倒れます.
忍耐は死体だというホソクは、あなたの攻撃に勝つために、守備手を自任した.ドミノの骨牌の初期状態と各ラウンドの2人の行動記録に基づいて、プログラムを作成してフォワードの点数とゲームカードの最終状態を出力します.

💎 入力

1行目は、ゲームボードの行数N、列数M、ラウンド数Rを与える.
次に、N行ゲームボードの状態をあげます.1行目から、M個の数字は、各メッシュに配置されたドミノの骨牌の長さを表す.
続いてR×2本の線の間にフォワードとバックの行動がある.各ラウンドは2列で構成され、1列目はフォワード、2列目は後衛の行動である.フォワードの行動は「X Y D」.これはX行Y列のドミノの骨牌をD方向に押すことを意味する.DはE、W、S、Nの1つで、それぞれ東、西、南、北方を代表している.バックの動きに「X Y」が与えられる.これはX行Y列のドミノ骨牌を再構築することを意味する.
攻撃隊員が転んだ四角いドミノの骨牌を倒そうとすれば、何も起こらない.また、転倒したドミノの骨牌がなければ、守備をしなければならない時も何も起こらない.

💎 しゅつりょく

1行目にフォワードの点数を出力する.
次に、ゲームボードの状態をN行にわたって出力する.各メッシュは、転んだFをスペースで区切っており、転んだSはありません.

💎 制限

入力した値はすべて正の整数です.

1 ≤ N, M ≤ 100

1 ≤ R ≤ 10,000

1≦ドミノ骨牌長≦5

フォワードとバックはオフサイドを取らない.

💎 解答方法

問題を見て少し慌てて、思ったより簡単でした.よく読むと分かりやすく、適用方法でやれば簡単に解決できるはずです!
重要な点は、ドミノを倒したときにドミノの骨牌の長さがどのように更新されるか、すでに転んだドミノの骨牌をどう考えるかだけを考えるとeasy~の問題です.
問題解決のため,int型Dominoアレイとchar型stateアレイを発表し,ドミノ骨牌の大きさとドミノ骨牌が倒れているか立っているかを決定した.攻撃者による攻撃のR回数では,ドミノの骨牌の大きさから転倒したドミノの骨牌を計算し,状態を適用することができる.

		.
		.
		.
        int n, m;
        char way;
        cin >> n >> m >> way;
        int count = domino[n][m];
        if(way == 'E'){
            while(count != 0 && m <= M){
                if(state[n][m] == 'S'){
                    count = max(count, domino[n][m]);
                    state[n][m] = 'F';
                    result++;
                }
                m++;
                count--;
            }
        }
        .
        .
        .

したがって,上のコードのようにn行m列に位置するドミノ骨牌を基準に,東,西,南,北中の一方向を特定し,ドミノ骨牌が転倒する過程を完了する.このときcountという変数によって、ドミノの骨牌の大きさは方向に従って一つ一つ減少し、自分よりも大きなドミノの骨牌に遭遇すると、その大きさはドミノの骨牌の大きさに従う.
そこで、立っているドミノの骨牌に出会ったら、ドミノの骨牌の大きさを確認して、更新するかどうかを決め、ドミノの骨牌を転倒状態に変換して、転倒したドミノの骨牌を計算することができます!また,ドミノ骨牌の大きさが0であるか,あるいは設定したN,Mの大きさを超える2次元配列のドミノ骨牌であれば,この繰り返しを終わらせることができる.
他の内容は本当に問題に沿って表現すればいいので、上に注意しなければなりません!

💎 完全なコード

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int domino[101][101];
char state[101][101];
int N, M, R;

int main(int argc, const char * argv[]) {
    
    cin >> N >> M >> R;
    memset(state, 'S', sizeof(state));
    
    for(int i = 1;i <= N;i++){
        for(int j = 1;j <= M;j++){
            cin >> domino[i][j];
        }
    }
    int result = 0;
    while(R--){
        int n, m;
        char way;
        cin >> n >> m >> way;
        int count = domino[n][m];
        if(way == 'E'){
            while(count != 0 && m <= M){
                if(state[n][m] == 'S'){
                    count = max(count, domino[n][m]);
                    state[n][m] = 'F';
                    result++;
                }
                m++;
                count--;
            }
        }
        else if(way == 'W'){
            while(count != 0 && m > 0){
                if(state[n][m] == 'S'){
                    count = max(count, domino[n][m]);
                    state[n][m] = 'F';
                    result++;
                }
                m--;
                count--;
            }
        }
        else if(way == 'S'){
            while(count != 0 && n <= N){
                if(state[n][m] == 'S'){
                    count = max(count, domino[n][m]);
                    state[n][m] = 'F';
                    result++;
                }
                n++;
                count--;
            }
        }
        else{
            while(count != 0 && n > 0){
                if(state[n][m] == 'S'){
                    count = max(count, domino[n][m]);
                    state[n][m] = 'F';
                    result++;
                }
                n--;
                count--;
            }
        }
        int standX, standY;
        cin >> standX >> standY;
        state[standX][standY] = 'S';
    }
    cout << result << "\n";
    
    for(int i = 1;i <= N;i++){
        for(int j = 1;j <= M;j++){
            cout << state[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

💎 悶える

久しぶりに開発をアップロードして、やり続けて、後、、、、学期が始まって、確かに忙しくなりました.周末にアルゴリズムを作る时、私はとても悩んでいる问题を整理したいですが、容易ではありません.3月はもう过ぎて、4月はもう1年の第1四半期を过ぎて、1つ1つやっていて、やはり仕事をしているような気がします.アルゴリズムを続けましょう.でも学期中は必ず部活と一緒に授業をしますよ~~
がんばって!