7

我遇到了一个面试问题“建议您将用于蛇和梯子游戏的数据结构？”

我会使用 2D 数组（与我们在国际象棋中所做的相同）来设计每个游戏块。但是是否可以将其设计为一维数组？许多人提出了这一建议，但没有人解释如何做到这一点。

4

8 回答 8

16

蛇和梯的规则是：

  1. 这个游戏有两个玩家，棋盘大小是 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，它包含当前位置作为键，下一个位置作为值。我认为一个 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;
                }                 
        }
       }
     }
  }
于 2015-01-03T11:51:13.240 回答
4

瓦赫是正确的。“是的，这是可能的：每个二维数组都可以表示为一维数组。”

数组

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

IE

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

@Jan Dvorak，“锯齿状数组不是二维数组”

于 2013-08-31T16:52:53.433 回答
1

在我博客的实现中，我使用了一对简单的链表来存储蛇和梯子。列表的每个元素都有一对方格，“from”方格和“to”方格；如果您降落在任何“从”方格，您的作品将被重新定位到“至”方。我发现最小游戏长度为 7 回合，平均游戏长度为 33 回合。您可以交替使用一维数组，其中数组的索引表示“从”正方形，数组中的值表示“到”正方形，除了在蛇的开头或索引之外，它与索引相同梯子。

于 2013-08-31T11:33:05.980 回答
1

为什么没有人建议使用 Map 作为数据结构。如果没有蛇或梯子，我们会将整数映射到自身。在蛇的情况下，我们将蛇的头部映射到它的尾巴，类似地也用于梯子。我们可以为每个玩家使用整数变量。

于 2014-12-08T05:22:37.157 回答
0

由于 Snakes/Chutes 和 Ladders 中的移动通常是单一方向的，而不是 Chess 中可能的多个方向，所以一维数组或列表肯定可以工作。

为了表示蛇和梯子，您可以将每个列表元素的内容设置为整数，告诉游戏当您降落在计数器上时向前或向后跳过多远。例如，在 Python 中：

# create a 5x5 board
board = [0 for i in range(25)]
# put a ladder in square 3, that moves you to square 10
board[2] = 7
# put a snake in square 14, that moves you to square 9
board[13] = -5
于 2013-08-31T11:05:00.030 回答
0

是的，这是可能的：每个二维数组都可以表示为一维数组。

在一维数组中依次表示二维数组的所有行。这样做，2d[i][j]就变成了1d[i * rowLength + j]。除非您别无选择，只能使用一维数组，否则这通常不是一件好事，因为它变得不那么可读且不易于使用。

于 2013-08-31T11:05:34.817 回答
0

使用数组：

int SNL[100];

根据以下规则，该数组的每个元素都包含一个整数：

  1. 如果有一个从xto开始的梯子x+l，那么SNL[x]=l;
  2. 如果有一条蛇咬在x并离开你x-s，那么SNL[x]=-s;，否则SNL[x]=0;
于 2014-03-06T16:12:37.407 回答
0

当然我们可以使用一维数组来解决这个问题，因为板上标记的数字是从 1 到 100。我们可以初始化两个一维数组：蛇和梯子，大小都是 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;
}
于 2014-11-03T16:47:11.523 回答