C++ Zuma游戏

让我们考虑一下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和hand作为参数。
  • s := s + "#"
  • 定义一个大小为26的数组v
  • for i := 0 to size of hand -1 do −
    • v[hand[i] - 'A'] ++
  • ret := solve(s, v)
  • return ret >= INF ? -1 : ret
  • 定义一个函数`solve()`，它将接收s和数组v作为参数。
  • if s == "#", then −
    • return 0
  • ret := INF
  • for i := 0, j := 0 to size of s - 1 do −
    • if s[i] == s[j], then −
      • 跳过本次迭代
    • need := 3 - (j - i)
    • x := s[i]
    • if need <= v[x - 'A'], then −
      • v[x - 'A'] -= need
      • ret := min(ret, need + solve(s.substring(0, i) + s.substring(j), v))
      • v[x - 'A'] += need
    • i := j
  • process(s)
  • if s == "#", then −
    • return 0
  • for i := 0, j := 0 to size of s - 1 do −
    • if s[i] == s[j], then −
      • 跳过本次迭代
    • need := 3 - (j - i)
    • x := s[i]
    • if need <= v[x - 'A'], then −
      • v[x - 'A'] -= need
      • ret := min(ret, need + solve(s.substring(0, i) + s.substring(j), v))
      • v[x - 'A'] += need
    • i := j
  • return ret
  • 定义一个函数`process()`，它将接收s作为参数。
  • for i := 0, j := 0 to size of s - 1 do −
    • if s[i] == s[j], then −
      • 跳过本次迭代
    • if (j - i) >= 3, then −
      • 从s中删除i到j之间的字符
      • j := i - 1
    • 否则
      • i := j
  • 使用两个字符串调用`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

更新于：2020年6月1日

672 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告