C ++中的Zuma游戏
让我们考虑一下祖玛游戏。假设我们在桌子上有一排球，这些球的颜色分别为红色(R)，黄色(Y)，蓝色(B)，绿色(G)和白色(W)。我们也有几个球。
现在，每次我们都可以从侧面选择一个球，然后将其插入行中。然后，如果有一组3个或以上相同颜色的球，则将其除去。继续这样做，直到无法取出更多球为止。
我们必须找到要插入的最小球，以删除桌子上的所有球。如果我们不能去除所有球，则返回-1。
因此，如果输入像“WRRBBW”，而我们有“RBW”，则答案将为3。我们可以在RR之后添加R，（WRR[R]BBW），删除后，序列将为(WBBW)，然后添加B，因此（WBB[B]W），删除后将为(WW)，然后添加W，因此序列将为（WW[W]）。这将删除所有球。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数findMinStep()，这将花费s，
s：=s连接“#”
定义大小为26的数组v
对于初始化i：=0，当i<手的大小，更新（将i增加1）时，执行-
将v[hand[i]-'A']增加1
ret：=调用函数solve(s,v)
返回ret>=如果INF不为零，则使用-1进行检查，否则使用ret
定义一个函数solve()，它将使用s，数组v，
如果s与“#”相同，则-
返回0
ret：=INF
对于初始化i：=0，j：=0，当j<s的大小时，更新（j增加1），-
v[x-'A']=v[x-'A']-需要
ret：=ret的最小值，需要+solve（s的子串从0到第i个索引）将s的子串从j串联到s的大小–j，v
v[x-'A']=v[x-'A']+需要
忽略以下部分，跳至下一个迭代
如果s[i]与s[j]相同，则-
需要：=3-(j-i)
x：=s[i]
如果需要<=v[x-'A']，则-
i：=j
调用函数过程
如果s与“#”相同，则-
返回0
对于初始化i：=0，j：=0，当j<s的大小时，更新（j增加1），-
v[x-'A']=v[x-'A']-需要
ret：=ret的最小值，需要+solve（s的子串从0到第i个索引）将s的子串从j串联到s的大小–j，v
v[x-'A']=v[x-'A']+需要
忽略以下部分，跳至下一个迭代
如果s[i]与s[j]相同，则-
需要：=3-(j-i)
x：=s[i]
如果需要<=v[x-'A']，则-
i：=j
返回ret
定义一个函数process()，它需要s，
对于初始化i：=0，j：=0，当j<s的大小时，更新（j增加1），-
i：=j
从s删除i，j-i
j：=i-1
忽略以下部分，跳至下一个迭代
如果s[i]与s[j]相同，则-
如果(j-i)>=3，则-
除此以外
用两个字符串调用findMinStep()以获取答案
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
class Solution {
public:
int findMinStep(string s, string hand) {
s += "#";
vector <int> v(26);
for(int i = 0; i < hand.size(); i++){
v[hand[i] - 'A']++;
}
int ret = solve(s, v);
return ret >= INF ? -1 : ret;
}
int solve(string s, vector <int>& v){
if(s == "#") return 0;
int ret = INF;
for(int i = 0, j = 0; j < s.size(); j++){
if(s[i] == s[j]) continue;
int need = 3 - (j - i);
char x = s[i];
if(need <= v[x - 'A']){
v[x - 'A'] -= need;
ret = min( ret, need + solve(s.substr(0,i) + s.substr(j , s.size() - j), v));
v[x - 'A'] += need;
}
i = j;
}
process(s);
if(s == "#") return 0;
for(int i = 0, j = 0; j < s.size(); j++){
if(s[i] == s[j]) continue;
int need = 3 - (j - i);
char x = s[i];
if(need <= v[x - 'A']){
v[x - 'A'] -= need;
ret = min( ret, need + solve(s.substr(0,i) + s.substr(j , s.size() - j), v));
v[x - 'A'] += need;
}
i = j;
}
return ret;
}
void process(string& s){
for(int i = 0, j = 0; j < s.size(); j++){
if(s[i] == s[j]) continue;
if((j - i) >= 3){
s.erase(i, j - i);
j = i - 1;
} else i = j;
}
}
};
main(){
Solution ob;
cout << (ob.findMinStep("WRRBBW", "RBW"));
}输入值
"WRRBBW", "RBW"
输出结果
3