LeetCode - 488. Zuma Game (DFS)题目链接题目解析看题目中的三个例子:DFS过程:先用一个map保存hand字符串中每种颜色的个数；dfs过程，遍历当前board字符串，逐. 博文 来自： 博客已搬家到GitHub，欢迎star^^. Zuma is a tile-matching puzzle video game published by PopCap Games.It can be played for free online at several websites, and was released for a number of platforms, including PDAs, mobile phones, and the iPod. An enhanced version, called Zuma Deluxe, was released for Microsoft Windows and Mac OS X as well as an Xbox Live Arcade download for the Xbox 360 and a PlayStation Network download for.
本题采用DFS求解，代码参考来自leetcode discussion, 地址如下
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.
Zuma Revenge
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’.
采用dfs,首先需要构造类似如下的结构
Zuma Game Leetcode Download
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代码如下