Zuma Game Algorithm

  1. Zuma Game Play Free Online
  2. Zuma Game Algorithm Free
  3. Zuma Game Algorithms
  4. Zuma Game Algorithm Game
  5. Zuma Game Algorithm Download
ZumaZuma Game Algorithm

Problem:

Zuma Game Play Free Online

Feb 27, 2020 A sorting algorithm is the fundamental of computer science, but we are getting ahead of ourselves. This is a fun puzzler where you try to come up with your own way to sort the tubes so each one end up with only one color.

Think about Zuma Game. You have a row of balls on the table, colored red(R), yellow(Y), blue(B), green(G), and white(W). You also have several balls in your hand.

Each time, you may choose a ball in your hand, and insert it into the row (including the leftmost place and rightmost place). Then, if there is a group of 3 or more balls in the same color touching, remove these balls. Keep doing this until no more balls can be removed.

Zuma Game Algorithm Free

Find the minimal balls you have to insert to remove all the balls on the table. If you cannot remove all the balls, output -1.

Examples:
Input: “WRRBBW”, “RB”
Output: -1
Explanation: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW

Input: “WWRRBBWW”, “WRBRW”
Output: 2
Explanation: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty

Input:“G”, “GGGGG”
Output: 2
Explanation: G -> G[G] -> GG[G] -> empty

Input: “RBYYBBRRB”, “YRBGB”
Output: 3
Explanation: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty

Algorithm

Note:

  1. You may assume that the initial row of balls on the table won’t have any 3 or more consecutive balls with the same color.
  2. The number of balls on the table won’t exceed 20, and the string represents these balls is called “board” in the input.
  3. The number of balls in your hand won’t exceed 5, and the string represents these balls is called “hand” in the input.
  4. Both input strings will be non-empty and only contain characters ‘R’,’Y’,’B’,’G’,’W’.

Idea: Search

Solution1: C++ / Search

Zuma Game Algorithms

2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46
48
50
52
54
56
// Runtime: 3 ms
public:
vector<int>h(128,0);
returndfs(board,h);
private:
// Return the min # of balls needed in hand to clear the board.
intdfs(conststring&board,vector<int>&hand){
inti=0;
while(i<board.size()){
// board[i] ~ board[j - 1] have the same color
// Number of balls needed to clear board[i] ~ board[j - 1]
// Have sufficient balls in hand
// Remove board[i] ~ board[j - 1] and update the board
stringnb=update(board.substr(0,i)+board.substr(j));
// Find the solution on new board with updated hand
intr=dfs(nb,hand);
// Recover the balls in hand
}
}
}
// Update the board by removing all consecutive 3+ balls.
stringupdate(stringboard){
while(i<board.size()){
while(j<board.size()&&board[i]board[j])++j;
board=board.substr(0,i)+board.substr(j);
}else{
}
returnboard;
};

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Zuma Game Algorithm Game

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物（任意商品）来支持我们

Zuma Game Algorithm Download

Venmo
huahualeetcode