我看到了一个面试问题：“为蛇和梯子游戏建议使用哪些数据结构？”
我会使用一个二维数组（就像我们在象棋中做的那样）来设计游戏的每个方块。但是是否可能在一个一维数组中设计它？许多人建议这样做，但没有人解释如何做到。
用于“贪吃蛇与梯子”游戏的数据结构
7
- user2714823
1
为了方便实现：https://codepumpkin.com/snakes-n-ladders/ - nitinsridar
8个回答
16
蛇和梯子的规则如下：
- 此游戏有两名玩家，棋盘大小为100（10×10）。
- 通过掷骰子可能出现的结果为1、2、3、4、5、6。
- 如果输出是6，则当前玩家将再次有机会掷骰子。
- 如果骰子的结果为1、2、3、4、5、6，且玩家位于蛇口，则其当前位置将改变为蛇尾，并且在掷出值为6的骰子之前，他将不能再次获取机会。
- 如果骰子的结果为1、2、3、4、5、6，且玩家位于梯子下方，则其当前位置将改变为梯子最高点的位置，并且他将再次获得掷骰子的机会。
- 如果玩家当前位置+掷出的点数>100，则需要考虑以下情况： i. 如果投掷出的数为6，则当前玩家将再次有机会，否则将轮到另一名玩家。
- 任何一名玩家比对手更早达到100分将成为胜者，游戏结束。
我们只传递一个包含当前位置为键和下一个位置为值的HashMap，我认为一个HashMap就足够完成所有梯子和蛇的要求了。
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;
}
}
}
}
}
- Neelabh Singh
4
Vakh是正确的。
“是的，这是可能的：每个二维数组都可以表示为一个一维数组。”
数组：
即（i.e.）
@Jan Dvorak， "jagged arrays 不是 2D 数组"
数组：
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
即（i.e.）
r = r + s + board[r+s-1])
@Jan Dvorak， "jagged arrays 不是 2D 数组"
- Siddique
1
为什么没有人建议使用Map作为数据结构。如果没有蛇或梯子，我们将把整数映射到它自身。在蛇的情况下，我们将蛇的头部映射到其尾部，梯子也是如此。我们可以为每个玩家使用整数变量。
- Praveen Kumar
1
在我的博客实现中，我使用了一对简单的链表来存储蛇和梯子。列表的每个元素都有一对方块，即“from”方块和“to”方块；如果你降落到任何一个“from”方块上，你的棋子就会被重新定位到“to”方块上。我发现游戏最少需要7个回合，平均需要33个回合。您也可以选择使用一维数组，其中数组的索引表示“from”方块，数组中的值表示“to”方块，除了在蛇或梯子的开头，这时候值与索引不同。
- user448810
0
由于蛇和梯子游戏通常只有一个方向，而不像国际象棋那样有多个方向，因此使用一维数组或列表肯定可以解决问题。
为了表示蛇和梯子，您可以将每个列表元素的内容设置为整数，告诉游戏当您落在该位置时要跳过多少格。例如，在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
- Ian Knight
0
当然我们可以使用一维数组来解决这个问题，因为在棋盘上标记的数字是从1到100。我们可以初始化两个一维数组：蛇和梯子，都是100大小的数组。
如果玩家在蛇头处（假设在56号格子），那么它必须移动到蛇尾（假设在6号格子）。然后蛇[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;
}
- Apurva Sharma
0
是的，这是可能的：每个二维数组都可以表示为一个一维数组。
将二维数组的所有行依次放在一个一维数组中。这样做，2d[i][j] 变成了 1d[i * rowLength + j]。除非你别无选择只能使用一维数组，否则通常不建议这样做，因为它变得更加难以阅读和使用。
- Jean Logeart
1
每个二维数组都可以表示为一个一维数组，但是不规则数组很难表示为单个一维数组，并且无法高效地进行索引。你是不是想说“每个矩形数组”？我知道这有点迂腐... :-) - John Dvorak
0
使用数组：
int SNL[100];
该数组的每个元素都包含一个整数，根据以下规则：
- 如果有一条从
x开始到x+l的梯子，则SNL[x]=l; - 如果在
x处被蛇咬并离开你到达x-s，则SNL[x]=-s;，否则SNL[x]=0;
- user3389076
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接