algorithm - Snake and Ladder ゲームで使用されるデータ構造

Question

「スネーク＆ラダーゲームに使用するデータ構造を教えてください」というインタビューの質問に出くわしました。

ゲームの各ブロックを設計するために、2D 配列 (チェスで行うのと同じ) を使用します。しかし、1D配列で設計することは可能ですか? 多くの人がこれを提案しましたが、誰もそれを行う方法を説明していません.

Answer 1

スネークとラダーのルールは次のとおりです。

1. このゲームには 2 人のプレイヤーがいて、ボードのサイズは 100 (10 X 10) です。
2. サイコロを投げて可能な結果は、1、2、3、4、5、6 です。
3. 出力が 6 の場合、現在のプレイヤーは再びサイコロを投げる機会を得ます。
4. サイコロの結果が 1,2,3,4,5,6 で、プレーヤーが蛇の口にいる場合、現在の位置は蛇の尾に変わり、価値のあるサイコロを投げるまで他のチャンスはありません。 6.
5. サイコロの結果が 1、2、3、4、5、6 で、プレイヤーがはしごの下にいる場合、現在の位置ははしごの一番上の位置に変わり、もう一度サイコロを振るチャンスが得られます。
6. プレーヤーの現在の位置 + ロール > 100 の場合、次の点を考慮してください i. if(roll==6) 現在のプレイヤーが再びチャンスを得る、そうでなければ他のプレイヤーが得る。
7. 他のプレイヤーよりも早く 100 に到達したプレイヤーが勝者となり、ゲームは終了します。

現在の位置をキーとして、次の位置を値として含む HashMap を 1 つだけ渡します。1 つの HashMap で Ladder と Snake のすべての要件が満たされると思います。

int playSnakeAndLadder(HashMap<Integer, Integer> hashMap){
    int player1=1, player2=1;// Initial position of players
    int chance=0;// This value show the change of players if chance is odd then player1 will play
                 // if chance is even then player2 will play
    while(1){
        if((player1==100)||(player2==100))// if any of player's position is 100 return chance;
            return chance;// Here chance shows who win the game, if chance is even player1 wins other //wise player2 wins
    int roll=Randon(6);// this will generate random number from 1 to 6.
    if(chance%2==0){
         int key=roll+player1;// new position of player1             
         boolean isLadder=false;// This is for checking the turn current player if againTurn is ture 
         // then the current player will player again.
         if(hashMap.contains(Key)){
             player1=hashMap.getValue(Key);
             // Here player current position will automatically update according to the hashMap.
             // if there is a snake the key value is greater than it mapping value.
             // if there is a ladder then key value is less than it mapping value. 
             if(Key<hashMap.getValue(Key))
                 isLadder=true;// Here player gets ladder.
             if(isLadder==true && roll==6 || isLadder==true)
               chance=chance;
             else
               chance=(chance+1)%2;
         }
         else if(player1+roll>100 && roll!=6)
               chance=(chance+1)%2;
            else if(player1+roll>100 && roll==6)
               chance=chance;
            else if(roll==6){
               player1=player1+roll;
               chance=chance;
            }
            else{
               player1=player1+roll;
               chance1=(chance1+1)%2;
            }                 
       }


    else{// Now similarly for player2
              {
             int key=roll+player2;// new position of player2             
             boolean isLadder=false;// This is for checking the turn current player if againTurn is ture 
             // then the current player will player again.
             if(hashMap.contains(Key)){
                 player2=hashMap.getValue(Key);
                 // Here player current position will automatically update according to the hashMap.
                 // if there is snake the key value is greater than it mapping value.
                 // if there is ladder then key value is less than it mapping value. 
                 if(Key<hashMap.getValue(Key))
                     isLadder=true;// Here player gets ladder.
                 if(isLadder==true && roll==6 || isLadder==true)
                   chance=chance;
                 else
                   chance=(chance+1)%2;
             }
             else if(player2+roll>100 && roll!=6)
                   chance=(chance+1)%2;
                else if(player2+roll>100 && roll==6)
                   chance=chance;
                else if(roll==6){
                   player2=player2+roll;
                   chance=chance;
                }
                else{
                   player2=player2+roll;
                   chance=(chance+1)%2;
                }                 
        }
       }
     }
  }

Answer 2

Vakhは正しいです。「はい、可能です。すべての 2D 配列を 1D 配列として表すことができます。」

配列

int board[100] =
{
     0,  0,  0, 10,  0,  0,  0,  0, 22,  0,
     0,  0,  0,  0,  0,  0,-10,  0,  0, 18,
     0,  0,  0,  0,  0,  0,  0, 56,  0,  0,
     0,  0,  0,  0,  0,  0,  0,  0,  0, 19,
    17,  0,  0,-20,  0,  0,  0,  0,  0,  0,
     0,-43, 18, -4,  0,  0,  0,  0,  0,  0,
    20,  0,  0,  0,  0,  0,  0,  0,  0,  0,
     0,  0,  0,  0,  0,  0,  0,-63,  0,  0,
     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
     0,  0,-20,  0,-20,  0,  0,  0,-21,  0
};

はしご 4->14、9->13、20->38、28->84、40->59、51->67、63->81、71->91、ヘビ 17->7、54 を保持できます->34、62->19、64->60、87->24、93->73、95->75、99->78

赤の位置が 2 (つまり r=2) でスコアが 2 (つまり s=2) の場合、赤の新しい位置は

    2+2+board[2+2-1] = 14

すなわち

    r = r + s + board[r+s-1])

@Jan Dvorak、「ギザギザの配列は 2D 配列ではありません」

Answer 3

ボード上にマークされた数字は 1 から 100 までであるため、1D 配列を使用して問題を解決できます。2 つの 1D 配列を初期化できます: ヘビとはしごは両方とも 100 サイズです。プレーヤーがスネーク ヘッド (56 と仮定) の場合、そのテール (6 と仮定) に移動する必要があります。次に、snake[56] = 6 (ルールに従って) プレーヤーは、6 としてマークされたブロックに移動します。はしご配列についても同様です。プレーヤーがスネーク ヘッドにいて、そのテールにナビゲートし、はしごが見つかった場合とその逆の場合について説明しました。擬似コードは次のとおりです。

int snake[101], ladder[101];
void SnakeAndLadder()
{
    int player_1=1, player_2=1, turn_player_1 = 1, a;
    while(1)
    {
        a = rand()%6 +1;
        if(turn_i==1)
        {
            turn_player_1 = 0;
            player_1 = takeStep(player_1+a);
            if(player_1==100)
            {
                cout<<"Player 1 won";
                break;
            }
        }
        else
        {
            turn_player_1 = 1;
            player_2 = takeStep(player_2+a);
            if(player_2==100)
            {
                cout<<"Player 2 won";
                break;
            }
        }
    }
}

int takeStep(int i)
{
    if(i<100)
    {
    if(snake[i]!=0 && i!=100)
    {
        i = snake[i];
    }
    if(ladder[i]!=0 && i!=100)
    {
        i = ladder[i];
        if(snake[i]!=0 && i!=100)
        {
            i= snake[i];
        }
    }
    }
return i;
}

Answer 4

配列の使用:

int SNL[100];

この配列のすべての要素には、次の規則に従って整数が含まれます。

1. xから始まるはしごがある場合x+l、SNL[x]=l;
2. にヘビに噛まれxて にあなたを残したらx-s, その後SNL[x]=-s;, そうでなければSNL[x]=0;