Cấu trúc dữ liệu sử dụng cho rắn và thang game

Question

Tôi đã xem qua một câu hỏi phỏng vấn "Đề nghị các cấu trúc dữ liệu mà bạn sẽ sử dụng cho rắn & thang trò chơi?"

tôi sẽ sử dụng một mảng 2D (giống như chúng ta làm trong cờ vua) để thiết kế từng khối trò chơi. Nhưng nó có thể thiết kế nó trong mảng 1D? Nhiều người đã đề xuất điều này nhưng không ai giải thích cách thực hiện.

Answer 1

Rules cho rắn và Ladder là:

1. Có hai người chơi trong trò chơi này và hội đồng quản trị kích thước là 100. (10 X 10)
2. kết quả có thể xảy ra bằng cách ném một con xúc xắc là 1,2 , 3,4,5,6.
3. Nếu đầu ra là 6 thì người chơi hiện tại sẽ có cơ hội một lần nữa để ném Dice.
4. Nếu kết quả của xúc xắc là 1,2,3,4,5,6 và người chơi định vị trên miệng rắn thì vị trí hiện tại của anh ta sẽ đổi thành đuôi rắn, và anh ta sẽ không có cơ hội khác cho đến khi anh ta ném một con xúc xắc có giá trị 6.
5. Nếu kết quả của Dice là 1,2,3,4,5,6 và người chơi được đặt ở bên dưới bậc thang thì vị trí hiện tại của anh ta sẽ thay đổi vị trí trên cùng của bậc thang và anh ta sẽ có cơ hội khác ném con xúc xắc lần nữa.
6. Nếu vị trí hiện tại của người chơi + cuộn> 100 thì hãy cân nhắc những điều sau đây i. nếu (roll == 6) người chơi hiện tại sẽ có cơ hội một lần nữa, nếu không người chơi khác sẽ nhận được.
7. Bất kỳ trình phát nào đạt đến 100 sớm hơn người chơi khác sẽ là người chiến thắng và trò chơi sẽ kết thúc.

Chúng tôi chỉ chuyển một HashMap, chứa vị trí hiện tại làm khóa và vị trí tiếp theo làm giá trị.Tôi nghĩ một HashMap sẽ hoàn thành tất cả các yêu cầu của Ladder và 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

Kể từ khi di chuyển trong Snakes/Chutes và Ladders thường theo một hướng, thay vì nhiều hướng có thể trong Chess, một mảng hoặc danh sách 1D chắc chắn sẽ hoạt động.

Để đại diện cho rắn và thang, bạn có thể đặt nội dung của từng phần tử danh sách thành số nguyên, cho trò chơi biết cách bỏ qua bộ đếm của bạn trước hoặc sau khi bạn truy cập. Ví dụ: trong 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 

Answer 3

Có thể có: mỗi mảng 2D có thể được biểu diễn dưới dạng mảng 1D.

Trình bày tất cả các hàng của dãy ô 2D trong dãy 1D. Làm như vậy, 2d[i][j] trở thành 1d[i * rowLength + j]. Trừ khi bạn không có lựa chọn nào khác ngoài việc sử dụng mảng 1d, nó thường không phải là một điều tốt để làm vì nó trở nên ít dễ đọc hơn và ít dễ sử dụng hơn.

Answer 4

Trong implementation tại blog của tôi, tôi đã sử dụng một cặp danh sách liên kết đơn giản để lưu trữ rắn và thang. Mỗi phần tử của danh sách có một cặp hình vuông, hình vuông "từ" và hình vuông "đến"; nếu bạn đã hạ cánh trên bất kỳ hình vuông nào "từ", mảnh của bạn đã được di chuyển đến hình vuông "đến". Tôi tìm thấy độ dài trò chơi tối thiểu là 7 lượt và thời lượng trò chơi trung bình là 33 lượt. Bạn có thể luân phiên sử dụng mảng một chiều, trong đó chỉ mục của mảng cho biết hình vuông "từ" và giá trị trong mảng đại diện cho hình vuông "đến", giống như chỉ mục ngoại trừ lúc bắt đầu của một con rắn hoặc thang.

Answer 5

Vakh là chính xác. "Có thể: mọi mảng 2D có thể được biểu diễn dưới dạng mảng 1D".

Mảng

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 
}; 

thể giữ thang 4> 14, 9> 13, 20-> 38, 28-> 84, 40-> 59, 51.> 67, 63-> 81, 71-> 91 và rắn 17-> 7, 54-> 34, 62-> 19, 64-> 60, 87-> 24, 93-> 73, 95-> 75, 99-> 78

nếu màu đỏ là ở vị trí thứ 2 (tức là r = 2) và điểm 2 (tức là s = ​​2) vị trí sau đó mới màu đỏ là

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

tức là

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

@Jan Dvorak, "mảng lởm chởm là mảng không 2D"

Answer 6

Sử dụng Array:

int SNL[100]; 

mọi phần tử của mảng này chứa một số nguyên theo quy tắc sau:

1. nếu có thang bắt đầu từ x đến.210, sau đó SNL[x]=l;
2. nếu có một vết rắn cắn tại x và để lại bạn tại x-s, sau đó SNL[x]=-s;, nếu không SNL[x]=0;

Answer 7

Chắc chắn chúng ta có thể giải quyết vấn đề sử dụng mảng 1D vì những con số đánh dấu trên tàu là từ 1 đến 100. Chúng ta có thể khởi tạo hai mảng 1D: con rắn và bậc thang cả 100 kích thước. Nếu người chơi ở đầu rắn (giả sử ở 56) thì nó phải di chuyển đến đuôi của nó (giả sử ở 6). Sau đó, rắn [56] = 6 (theo quy tắc), người chơi sẽ di chuyển đến khối được đánh dấu là 6. Tương tự cho mảng ladder. Tôi đã đề cập đến trường hợp người chơi ở đầu rắn và điều hướng đến đuôi của nó và có một cái thang và ngược lại. Mã giả là:

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 8

Tại sao không ai đề xuất sử dụng Bản đồ làm cấu trúc dữ liệu. Chúng tôi sẽ ánh xạ số nguyên cho chính nó nếu không có con rắn hoặc bậc thang. Trong trường hợp con rắn chúng ta sẽ lập bản đồ phần đầu của con rắn vào đuôi của nó và tương tự cho cái thang. Chúng tôi có thể sử dụng biến số nguyên cho mỗi người chơi.