我看到了一个面试问题:“为蛇和梯子游戏建议使用哪些数据结构?”
我会使用一个二维数组(就像我们在象棋中做的那样)来设计游戏的每个方块。但是是否可能在一个一维数组中设计它?许多人建议这样做,但没有人解释如何做到。
我看到了一个面试问题:“为蛇和梯子游戏建议使用哪些数据结构?”
我会使用一个二维数组(就像我们在象棋中做的那样)来设计游戏的每个方块。但是是否可能在一个一维数组中设计它?许多人建议这样做,但没有人解释如何做到。
蛇和梯子的规则如下:
我们只传递一个包含当前位置为键和下一个位置为值的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;
}
}
}
}
}
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])
由于蛇和梯子游戏通常只有一个方向,而不像国际象棋那样有多个方向,因此使用一维数组或列表肯定可以解决问题。
为了表示蛇和梯子,您可以将每个列表元素的内容设置为整数,告诉游戏当您落在该位置时要跳过多少格。例如,在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
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;
}
是的,这是可能的:每个二维数组都可以表示为一个一维数组。
将二维数组的所有行依次放在一个一维数组中。这样做,2d[i][j]
变成了 1d[i * rowLength + j]
。除非你别无选择只能使用一维数组,否则通常不建议这样做,因为它变得更加难以阅读和使用。
int SNL[100];
该数组的每个元素都包含一个整数,根据以下规则:
x
开始到 x+l
的梯子,则 SNL[x]=l;
x
处被蛇咬并离开你到达 x-s
,则 SNL[x]=-s;
,否则 SNL[x]=0;