- Game Overview. Take a toad trip through the temple of Zuma®! Use the reptilian stone idol to match magical orbs and defeat an age-old curse!
- 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).
Zuma Deluxe
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.
本题采用DFS求解,代码参考来自leetcode discussion, 地址如下
https://discuss.leetcode.com/topic/76681/simple-c-dfs-solution-using-list
不过我进行了相关的改进和说明。
https://discuss.leetcode.com/topic/76681/simple-c-dfs-solution-using-list
不过我进行了相关的改进和说明。
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.
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.
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’.
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’.
采用dfs,首先需要构造类似如下的结构
RRBBBGYYWWWYB, 转化后的表示为[[“R”, 2], [“B”, 3], [“G”, 1], [“B”, 1]]
可以采用list进行存储(因为需要不断的调整,删除操作很多)
该开始没有封装一个堆list进行清除的函数,写的太乱,没做出来,参考了如下的
- 我的改进1
它写的cleanBoard(list<> &li; 函数是有问题的
比如对于“RBYYYBBRRRBRR”,是可以全部清除的,所以这个清除函数还是需要仔细考虑的(做到瞻前顾后)
- 我的改进2
对于hand字符串,可以采用map结构存储字符数量,使用一个就+1,回溯对应减操作
- 注意点
在dfs时候,需要明白何时进行cleanBoard操作,list是可以直接赋值操作的,对于list<>::iterator需要清清楚的认识 erase,prev,next等操作方法。
我的ac代码如下
Zuma Deluxe is a good old online game that has its origins in 2003.
The meaning of the game is to prevent the penetration of balls of different colors into the Gold skull. These balls are steadily moving in its direction along a spiral trajectory. The balls are destroyed by other balls of different colors that are emitted from the Frog, located in the central part of the playing field. Thus, to attack you need to shoot the ball of the same color into the group of at least two same colored balls. Otherwise, the impact ball is stuck in a spiral. During the game you need to destroy as many balls as possible, to collect the maximum of gold coins and various bonuses, and, of course, to prevent the penetration of the balls into the skull.
Zuma Deluxe belongs to the family of casual games for a wide range of users.The Frog is, in fact, the main hero of the game. Thanks to your efforts it accurately attacks the groups of moving balls.
The game has many levels. Each of them is given specific time.