[白俊]20165号我慢のドミノ骨牌職人

23958 ワード
白駿 algorithm テキストリンク
白駿20165号我慢のドミノ骨牌職人解答

問題の説明


人を怒らせる方法はいろいろあります.その中で最悪なのは、努力して立てたドミノの骨牌を倒すことだ.今回発売されたボードゲーム 「死ぬか生きるか」はそれを利用して、二人で攻撃と守備を行うゲームだ.攻撃手はドミノの骨牌を倒し続けた 守備員 ドミノの骨牌を作り続けます.本ゲームは以下のように行います.
  • N行M列の2次元メッシュゲームボード上の各メッシュ上 ドミノの骨牌を立てる.ドミノの骨牌ごとに1つまたは5つ以下の高さがあります.
  • ラウンドはフォワードが先に攻撃し、バックは攻撃が終わった後に守備した.
  • 攻撃手は、特定のグリルに置かれたドミノの骨牌を東、西、南、北の任意の方向に倒す.長さKの ドミノが特定の方向に転ぶと、その方向K-1個のドミノのうち転ばなかったものが同じ方向に次々と転ぶ.この場合、ドミノの特性上、ドミノが連続して転倒する可能性がある.転んだドミノの骨牌がある格子を攻撃すると、 何事も起こらない.
  • バックが欲しがっていたのは、転んだドミノの骨牌だった. 再構築 いいですよ.転んでいないドミノの骨牌を作りたいなら、何も起こらない.
  • ラウンドで、3、4番のプロセス 繰り返します.攻撃手がそのターンに転倒したドミノの数をラウンドごとに数え、Rターンの合計が攻撃手の点数となる.

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

    問題を見る考え

  • 実装問題なので、機能別に関数を区切っておけばいいです.

    • プールの概要


    図には
  • 東南北西方向が格納されている.
  • 攻撃後、ドミノの骨牌の位置と高さをクラブに蓄え、転倒を続けた.
  • 守備時に転倒したプレートの情報を知る必要があるため,初期プレート情報を格納したoriginBoardの2次元配列を発表した.

    • コード#コード#

    #include <iostream>
#include <map>
#include <queue>

#define MAX_N 100

using namespace std;

struct pos{
  int r, c;
  int height;
};

int N, M, R;
int originBoard[MAX_N+1][MAX_N+1];
int board[MAX_N+1][MAX_N+1];
map<char, pos> dir;

void setDir(){
  dir['E'] = {0, 1};
  dir['W'] = {0 , -1};
  dir['S'] = {1, 0};
  dir['N'] = {-1 , 0};
}

void getInput(){
  cin >> N >> M >> R;
  for(int r=1; r<=N; ++r){
    for(int c=1; c<=M; ++c){
      cin >> originBoard[r][c];
    }
  }
}

bool checkBound(int r, int c){
  return (r < 1 || c < 1 || r > N || c > M);
}

int attack(){
  pos p; cin >> p.r >> p.c;
  char dirChar; cin >> dirChar;
  pos d = dir[dirChar];

  int score = 0;
  queue<pos> q;
  q.push({p.r, p.c, board[p.r][p.c]});
  while(!q.empty()){
    pos curr = q.front(); q.pop();
    if(checkBound(curr.r, curr.c)){
      continue;
    }
    if(board[curr.r][curr.c] == -1){
      continue;
    }
    board[curr.r][curr.c] = -1;
    ++score;
    
    for(int i=1; i<curr.height; ++i){
      int nr = curr.r + d.r*i;
      int nc = curr.c + d.c*i;
      if(checkBound(nr, nc)){
        continue;
      }
      if(board[nr][nc] == -1){
        continue;
      }
      q.push({nr, nc, board[nr][nc]});
    }
  }

  return score;
}

void defense(){
  pos p; cin >> p.r >> p.c;
  if(board[p.r][p.c] != -1){
    return;
  }

  board[p.r][p.c] = originBoard[p.r][p.c];
}

void copyOriginBoard(){
  for(int r=1; r<=N; ++r){
    for(int c=1; c<=M; ++c){
      board[r][c] = originBoard[r][c];
    }
  }
}

void printBoard(){
  for(int r=1; r<=N; ++r){
    for(int c=1; c<=M; ++c){
      if(board[r][c] == -1){
        cout << "F ";
      } else{
        cout << "S ";
      }
    }cout << "\n";
  }
}

void solve(){
  setDir();
  getInput();
  copyOriginBoard();
  int score = 0;
  while(R--){
    score += attack();
    defense();
  }

  cout << score << "\n";
  printBoard();
}

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

  return 0;
}
    Bootstrapグローバルcssスタイル_コード#コード#
    白俊アルゴリズム14621号:私だけじゃダメな恋