488. 祖瑪游戲
你正在參與祖瑪游戲的一個變種。
在這個祖瑪游戲變體中，桌面上有 一排 彩球，每個球的顏色可能是：紅色 ‘R’、黃色 ‘Y’、藍色 ‘B’、綠色 ‘G’ 或白色 ‘W’ 。你的手中也有一些彩球。
你的目標是 清空 桌面上所有的球。每一回合：
從你手上的彩球中選出 任意一顆 ，然后將其插入桌面上那一排球中：兩球之間或這一排球的任一端。
接著，如果有出現 三個或者三個以上 且 顏色相同 的球相連的話，就把它們移除掉。
如果這種移除操作同樣導致出現三個或者三個以上且顏色相同的球相連，則可以繼續移除這些球，直到不再滿足移除條件。
如果桌面上所有球都被移除，則認為你贏得本場游戲。
重復這個過程，直到你贏了游戲或者手中沒有更多的球。
給你一個字符串 board ，表示桌面上最開始的那排球。另給你一個字符串 hand ，表示手里的彩球。請你按上述操作步驟移除掉桌上所有球，計算并返回所需的 最少 球數。如果不能移除桌上所有的球，返回 -1 。
示例 1：輸入：board = "WRRBBW", hand = "RB"
輸出：-1
解釋：無法移除桌面上的所有球。可以得到的最好局面是：
- 插入一個 'R' ，使桌面變為 WRRRBBW 。WRRRBBW -> WBBW
- 插入一個 'B' ，使桌面變為 WBBBW 。WBBBW -> WW
桌面上還剩著球，沒有其他球可以插入。示例 2：輸入：board = "WWRRBBWW", hand = "WRBRW"
輸出：2
解釋：要想清空桌面上的球，可以按下述步驟：
- 插入一個 'R' ，使桌面變為 WWRRRBBWW 。WWRRRBBWW -> WWBBWW
- 插入一個 'B' ，使桌面變為 WWBBBWW 。WWBBBWW -> WWWW -> empty
只需從手中出 2 個球就可以清空桌面。示例 3：輸入：board = "G", hand = "GGGGG"
輸出：2
解釋：要想清空桌面上的球，可以按下述步驟：
- 插入一個 'G' ，使桌面變為 GG 。
- 插入一個 'G' ，使桌面變為 GGG 。GGG -> empty
只需從手中出 2 個球就可以清空桌面。示例 4：輸入：board = "RBYYBBRRB", hand = "YRBGB"
輸出：3
解釋：要想清空桌面上的球，可以按下述步驟：
- 插入一個 'Y' ，使桌面變為 RBYYYBBRRB 。RBYYYBBRRB -> RBBBRRB -> RRRB -> B
- 插入一個 'B' ，使桌面變為 BB 。
- 插入一個 'B' ，使桌面變為 BBB 。BBB -> empty
只需從手中出 3 個球就可以清空桌面。
提示：
- 1 <= board.length <= 16
- 1 <= hand.length <= 5
- board 和 hand 由字符 ‘R’、‘Y’、‘B’、‘G’ 和 ‘W’ 組成
- 桌面上一開始的球中，不會有三個及三個以上顏色相同且連著的球
解題思路
使用樸素的回溯法：每次遞歸嘗試向board的每一個位置插入hand里面的每一顆球，插入以后檢查是否能出現三個或者三個以上 且 顏色相同 的球相連的話，并且把它們移除掉。
剪枝
- 使用set記錄已經遞歸過的情況
- 一旦當前遞歸的使用的球數小于了目前得出的最小球數
代碼
class Solution {
public:int m=0x3f3f3f3f;void dfs(int cnt,string hand,string board) {if (cnt>=m) return;if (set.count({board,cnt}))return;set.insert({board,cnt});if (board.empty()) {m=min(m,cnt);return;}if (hand.empty()) return;for (int i = 0; i < board.size(); ++i) {for (int j = 0; j < hand.size(); ++j) {char cur=hand[j];hand.erase(hand.begin()+j);string ns=board;ns.insert(ns.begin()+i,cur);handler(ns);dfs(cnt+1,hand,ns);hand.insert(hand.begin()+j,cur);}}}int findMinStep(string board, string hand) {dfs(0,hand, board);return m==0x3f3f3f3f ? -1 : m;}set<pair<string,int>> set ;void handler(string& s){int seq(1);for (int i = 1; i <= s.size(); ++i) {if (i<s.size()&&s[i]==s[i-1]) {seq++;continue;}if(seq>=3){s.erase(i-seq,seq);i=0;}seq=1;}}};
