[プログラマー/C++]クレーンゴーストゲーム


問題の説明


ゲーム開発者「Jordy」はクレーン型の抽出機をモバイルゲームに変えようとしている.
ゲームの面白さを高めるために、「Jordie」は画面レイアウトとルールをゲームロジックに反映し、以下のようにします.
ゲーム画面は「1 x 1」サイズのセルからなる「NxN」サイズの正斜角メッシュで、上部にクレーン、右側にバスケットがあります.(上の図は、サイズが「5 x 5」の例を示しています).各格子間には様々なぬいぐるみがあり、ぬいぐるみのない格子は空いています.すべての人形は「1 x 1」の大きさのメッシュを占め、メッシュの一番下から順番に積み上げられます.ゲームユーザーはクレーンを左右に動かし、停止した位置から一番上の人形を持ち上げることができる.拾った人形はかごの中に積み上げられ、かごの一番下の格子から人形は順番にかごの中に積み上げられます.下の図は[1番、5番、3番の位置で人形を順番にかごに入れる様子を示しています.

同じ形の2人の人形が連続してかごに積まれると、2人の人形が爆発してかごから消えてしまいます.上の状態で、次に[5番]の位置から人形をかごに積み上げると、同じ形の人形が2つ消えてしまいます.

クレーンが作動すると、人形が挟まないことはありませんが、人形がないところでクレーンを起動すれば、何も起こりません.また、バスケットが十分大きく、すべての人形を収容できると仮定します.(図中、スクリーン表示制限は5コマのみ表示)
ゲーム画面上の格子状態の2次元配列板と人形を挟むために、起動クレーンの位置を含む配列動作をパラメータとして指定した場合、solution関数を完了し、クレーンをすべて起動させ、爆発して消えた人形の個数を返します.

せいげんじょうけん

  • マザーボードアレイは2 Dアレイで、サイズは「5 x 5」または「30 x 30」より大きい.
  • boardの各セルには、0または100以下の整数が含まれています.
  • 0はスペースを表します.
  • 1-100の各数字は異なる人形の形を表し、同じ数字は同じ人形の形を表す.
  • モバイルアレイのサイズは1000を超えません.
  • movies配列の各要素の値は1より大きく、自然数であり、スラブ配列の水平寸法より小さい.
  • I/O例


    boardmovesresult[[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]][1,5,3,5,1,2,1,4]4

    I/O例説明

  • I/O 1
    人形の初期状態は、与えられた問題の例と同じである.
    クレーンは[1,5,3,5,1,2,1,4]号の位置から順番に人形を持ち上げ、かごに入れ、
    状態は下図のように、かごの中で爆発して消えた人形が4つあります.
  • 方法


    積み重ねられた人形の棒をスタックとして宣言し、抽出された人形の種類がスタックの上部と同じであればpopし、結果に2を加えて解放する.
    また,ぬいぐるみを抜く時間を減らすため,top rowではcolごとに最上位のぬいぐるみの位置(row)を保存した.

    コード#コード#

    #include <string>
    #include <vector>
    #include <stack>
    #include <iostream>
    
    using namespace std;
    
    int solution(vector<vector<int>> board, vector<int> moves) {
        int result = 0;
        int board_size = board[0].size();
        int move_kakao; //옮길 인형 종류
        stack<int> bar; //인형을 쌓을 막대
        int top_row[board_size]; // 각 col에 있는 인형의 최상단 위치(row)를 저장
        for (int col_idx = 0; col_idx < board_size; col_idx++)
            for(int row_idx = 0; row_idx < board_size; row_idx++)
                if (board[row_idx][col_idx] != 0)
                {
                    top_row[col_idx] = row_idx;
                    break;
                }
        for (int move : moves)
        {
            if (top_row[move - 1] >= board_size) // 움직일 인형이 없으면 넘어감
                continue;
            move_kakao = board[top_row[move - 1]][move - 1];
            board[top_row[move - 1]][move - 1] = 0;
            top_row[move - 1]++;
            if (!bar.empty() && bar.top() == move_kakao)
            {
                result += 2;
                bar.pop();
            }
            else
                bar.push(move_kakao);
        }
        return result;
    }

    提问链接