AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【剪枝】【广度优先】【深度优先】488祖玛游戏

2024-01-22 67
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【剪枝】【广度优先】【深度优先】488祖玛游戏

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’ 组成

桌面上一开始的球中，不会有三个及三个以上颜色相同且连着的球

剪枝

剪枝一：如果手中有多个相同颜色的球，只需要尝试一个，其它不需要尝试。

剪枝二：如果收中的球和桌面颜色相同的球，只需要考虑插入到最前面。在一个红球的前面或后面插入红球，结果一样两个连续的红球。在两个红球的前面或后面或中间插入红球的效果一样，连续的3个红球消除。

假定插入的颜色是ch，插入的位置是i，只需要考虑以下两种情况：

一，board[i]等于ch。

二，board[i-1]等于board[i]。

忽略剪枝后，再考虑这两种情况。这两种情况都是必须，缺少情况一，无法消除任何球。缺少情况二，无法消除以下用例：

RRWWRRBBRR WB，第一步消除W或B的连锁反应都会消除4个R，造成余下的2个R，无法消除。

RRWWRRBBRWR − − − > 消除 B _{--->}^{消除B}−−−>消除B RRWWRRRWR − − − − − − − − > 连锁消除 3 个 R _{-------->}^{连锁消除3个R}−−−−−−−−>连锁消除3个R RRWWWR − − − − − − − − > 连锁消除 3 个 W _{-------->}^{连锁消除3个W}−−−−−−−−>连锁消除3个WRRR− − − − − − − − > 连锁消除 3 个 W _{-------->}^{连锁消除3个W}−−−−−−−−>连锁消除3个W 结束。

下面来证明为什么只需要考虑两种情况：
0==i 两种相等 情况一
两种不等 假定ch能被消除，假定和ch同时消除，从左向右第一个小标为i1，board[0]和board[i1]一起被消除，说明board(0,i1)能被消除且不依赖不影响board[i1]，那将ch不插入到0，插入到i1，操作顺序完全一样。被淘汰。简称证明一。
board.length-1 == i 两者相等 就是剪枝二。
两者不等 类似证明一。
i是中间的下标 三者相等 剪枝二淘汰。
ch==board[i] 就是情况一。
ch==board[i-1] 就是剪枝二，淘汰。
board[i-1]==board[i] 就是情况二。
三者不等。 假定ch能被消除，否则则组合没有任何意义。一个ch无法消除，所以它的左边或边有必定有一个ch被一起消除。不失一般性，假定在它的左边，下标为i1，borad[i1]和ch一起被消除，说明(i1,i)的字符都消除。那将ch插入到i1和i的效果一样。由于board[i-1]不等于board[i]和ch，所以无论是否插入ch，都不会影响右边的字符。 两中方案(i1,i)的左边都是ch，所以新方案不会有影响左边。

第一版代码

class Solution {
public:
int findMinStep(string board, string hand) {
sort(hand.begin(), hand.end());
queue> que;
unordered_set setHasDo;
auto Add = [&](const string& s, const string& h)
{
bool bEmpty = s.empty();
const string cur = s + “-” + h;
if (setHasDo.count(cur))
{
return;
}
setHasDo.emplace(cur);
que.emplace(s, h);
};
Add(board, hand);
while (que.size())
{
auto [s, h] = que.front();
que.pop();
if (s.empty())
{
return hand.length() - h.length();
}
unordered_map mCharCount;
for (const auto& ch : h)
{
mCharCount[ch]++;
}
for (int j = 0; j < s.length(); j++)
{
if ((j + 1 < s.length()) && (s[j] == s[j + 1]))
{
if (mCharCount.count(s[j]) && (mCharCount[s[j]] >= 1))
{
mCharCount[s[j]]–;
Add(Do(s.substr(0,j+1)+s[j] + s.substr(j+1)),ToString(mCharCount));
mCharCount[s[j]]++;
}
for ( auto& [ch, iCnt] : mCharCount)
{
if (ch != s[j])
{
iCnt–;
Add(Do(s.substr(0, j+1) + ch + s.substr(j + 1)), ToString(mCharCount));
iCnt++;
}
}
}
else
{
if (mCharCount.count(s[j]) && (mCharCount[s[j]] >= 2))
{
mCharCount[s[j]] -= 2;
Add(Do(s.substr(0, j) + s[j] + s[j] + s.substr(j)), ToString(mCharCount));
mCharCount[s[j]] += 2;
}
}
}
}
return -1;
}
string Do(const string& s)
{
stack> sta;
for (const char& ch : s )
{
while (sta.size() && (sta.top().first != ch) && (sta.top().second >= 3))
{
sta.pop();
}
if (sta.size() && (sta.top().first == ch))
{
sta.top().second++;
}
else
{
sta.emplace(ch, 1);
}
}
string sRet;
while (sta.size())
{
const auto [ch, iCnt] = sta.top();
sta.pop();
if (iCnt < 3)
{//最后一个元素需要判断
sRet += string(iCnt, ch);
}
}
return sRet; //正序和反序是一样的
}
string ToString(const unordered_map& mCharCount)
{
string strRet;
for (const auto& [ch, iCnt] : mCharCount)
{
strRet += string(iCnt, ch);
}
return strRet;
}
}; ，

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  string board,  hand;  
  {
    Solution sln;
    board = "RRWWRRBBRR", hand = "WB";
    auto res = sln.findMinStep(board, hand);
    Assert(2, res);
  }
  {
    Solution sln;
    board = "WWRRBBWW", hand = "WRBRW";
    auto res = sln.findMinStep(board, hand);
    Assert(2, res);
  }
  {
    Solution sln;
    board = "G", hand = "GGGGG";
    auto res = sln.findMinStep(board, hand);
    Assert(2, res);
  }
  {
    Solution sln;
    board = "WRRBBW", hand = "RB";
    auto res = sln.findMinStep(board, hand);
    Assert(-1, res);
  }
  {
    Solution sln;
    board = "WRRBBW", hand = "RB";
    auto res = sln.findMinStep(board, hand);
    Assert(-1, res);
  }
  {
    Solution sln;
    board = "RBYYBBRRB", hand = "YRBGB";
    auto res = sln.findMinStep(board, hand);
    Assert(3, res);
  }
  {
    Solution sln;
    board = "RRGGBBYYWWRRGGBB", hand = "RGBYW";
    auto res = sln.findMinStep(board, hand);
    Assert(-1, res);
  }
}

小的优化

class Solution {
public:
  int findMinStep(string board, string hand) {
    sort(hand.begin(), hand.end());
    queue<pair<string,string>> que;
    unordered_set<string> setHasDo;
    auto Add = [&](const string& s, const string& h)
    {
      const string cur = s + "-" + h;
      if (setHasDo.count(cur))
      {
        return;
      }
      setHasDo.emplace(cur);
      que.emplace(s,h);
    };
    Add(board, hand);
    while (que.size())
    {
      auto[s,h] = que.front();
      que.pop();  
      if (s.empty())
      {
        return hand.length() - h.length();
      }
      for (int i = 0 ; i < h.length();i++)
      {
        if (i && (h[i] == h[i - 1]))
        {//剪枝一
          continue;
        }
        string h2 = h.substr(0,i) + h.substr(i+1);
        for (int j = 0; j < s.length(); j++)
        {
          if (j&& (h[i] == s[j-1]))
          {
            continue;//剪枝二
          }
          if ((h[i] == s[j])||(j && (s[j - 1] == s[j])))
          {
            Add(Do(s, j, h[i]), h2);
          }
        }
      }
    }
    return -1;
  }
  string Do(const string& s, int l1,  const char& ch)
  {   
    stack<pair<char,int>> sta;
    auto Add = [&sta](const char& ch)
    {
      while (sta.size() && (sta.top().first != ch ) && (sta.top().second >= 3))
      {
        sta.pop();
      }
      if (sta.size()&& (sta.top().first == ch))
      {
        sta.top().second++;
      }
      else
      {
        sta.emplace(ch,1);
      }     
    };
    for (int i = 0; i < l1; i++)
    {
      Add( s[i]);
    }
    Add(ch);
    for (int i = l1; i < s.length() ; i++)
    {
      Add(s[i]);
    }
    string sRet;
    while (sta.size())
    {
      const auto [ch,iCnt] = sta.top();
      sta.pop();
      if (iCnt < 3)
      {//最后一个元素需要判断
        sRet += string(iCnt, ch);
      }
    }
    return sRet; //正序和反序是一样的
  }
};

实际上只需要考虑三种情况

  • 弹出一个球，三消。
  • 弹出两个同颜色的球三消。
  • 两个同颜色的球直接插入不同颜色的球。
class Solution {
public:
  int findMinStep(string board, string hand) {
    sort(hand.begin(), hand.end());
    queue<pair<string, string>> que;
    unordered_set<string> setHasDo;
    auto Add = [&](const string& s, const string& h)
    {
      bool bEmpty = s.empty();
      const string cur = s + "-" + h;
      if (setHasDo.count(cur))
      {
        return;
      }
      setHasDo.emplace(cur);
      que.emplace(s, h);
    };
    Add(board, hand);
    while (que.size())
    {
      auto [s, h] = que.front();
      que.pop();
      if (s.empty())
      {
        return hand.length() - h.length();
      }
      unordered_map<char, int> mCharCount;
      for (const auto& ch : h)
      {
        mCharCount[ch]++;
      }     
      for (int j = 0; j < s.length(); j++)
      {
        if ((j + 1 < s.length()) && (s[j] == s[j + 1]))
        {
          if (mCharCount.count(s[j]) && (mCharCount[s[j]] >= 1))
          {
            mCharCount[s[j]]--;
            Add(Do(s.substr(0,j+1)+s[j] + s.substr(j+1)),ToString(mCharCount));
            mCharCount[s[j]]++;
          }
          for ( auto& [ch, iCnt] : mCharCount)
          {
            if (ch != s[j])
            {
              iCnt--;
              Add(Do(s.substr(0, j+1) + ch + s.substr(j + 1)), ToString(mCharCount));
              iCnt++;
            }
          }
        }
        else
        {
          if (mCharCount.count(s[j]) && (mCharCount[s[j]] >= 2))
          {
            mCharCount[s[j]] -= 2;
            Add(Do(s.substr(0, j) + s[j] + s[j] + s.substr(j)), ToString(mCharCount));
            mCharCount[s[j]] += 2;
          }
        }       
      }
    }
    return -1;
  }
  string Do(const string& s)
  {
    stack<pair<char, int>> sta;
    for (const char& ch : s )
    {
      while (sta.size() && (sta.top().first != ch) && (sta.top().second >= 3))
      {
        sta.pop();
      }
      if (sta.size() && (sta.top().first == ch))
      {
        sta.top().second++;
      }
      else
      {
        sta.emplace(ch, 1);
      }
    }
    string sRet;
    while (sta.size())
    {
      const auto [ch, iCnt] = sta.top();
      sta.pop();
      if (iCnt < 3)
      {//最后一个元素需要判断
        sRet += string(iCnt, ch);
      }
    }
    return sRet; //正序和反序是一样的
  }
  string ToString(const unordered_map<char, int>& mCharCount)
  {
    string strRet;
    for (const auto& [ch, iCnt] : mCharCount)
    {
      strRet += string(iCnt, ch);
    }
    return strRet;
  }
};

进一步改进

hand的状态可以用位运算来表示，这可以提速，本题已经够复杂了。就不继续了。

可以用 深度优先，但要处理重复搜索。

已有状态： board用字符串，字典树提速。 hand用int 提速。

2023年1月版

class Solution {
public:
int findMinStep(string board, string hand) {
std::sort(hand.begin(), hand.end());
m_iMaxStep = hand.size();
std::unordered_set pre;
pre.emplace(hand + board);
for (int iStep = m_iMaxStep; iStep > 0; iStep–)
{
std::unordered_set dp;
for (const auto str : pre)
{
const string sHand = str.substr(0, iStep);
const string sBoard = str.substr(iStep);
if (“” == sBoard)
{
return m_iMaxStep - iStep;
}
Do(dp, sBoard, sHand);
}
pre.swap(dp);
}
if (pre.count(“”))
{
return m_iMaxStep;
}
return -1;
}
void Do(std::unordered_set& dp, const string& strBoard, const string& strHand)
{
for (int i = 0; i < strHand.size(); i++)
{
if ((i>0) && (strHand[i] == strHand[i - 1]))
{
continue;
}
string tmp = strHand;
tmp.erase(i, 1);
const char& ch = strHand[i];
for (int j = 0; j <= strBoard.size(); j++)
{
bool bNeedDo = false;
if (j < strBoard.length() && (strBoard[j] == ch))
{
bNeedDo = true;
}
if (j>0)
{
if ((j < strBoard.length()) && (strBoard[j-1] == strBoard[j])&&(ch != strBoard[j]))
{
bNeedDo = true;
}
}
if (!bNeedDo)
{
continue;
}
dp.emplace(tmp + Do(strBoard, j, ch));
}
}
}
string Do(string strBoard, int index, const char& ch)
{
strBoard.insert(index, std::string(“”) + ch);
Erase(strBoard, index);
return strBoard;
}
void Erase(string& strBoard, int index)
{
string res;
vector> st;
for (auto c : strBoard) {
while (!st.empty() && c != st.back().first && st.back().second >= 3) {
st.pop_back();
}
if (st.empty() || c != st.back().first) {
st.push_back({ c, 1 });
}
else {
st.back().second++;
}
}
if (!st.empty() && st.back().second >= 3) {
st.pop_back();
}
for (int i = 0; i < st.size(); ++i) {
for (int j = 0; j < st[i].second; ++j) {
res.push_back(st[i].first);
}
}
strBoard = res;
}
int m_iMaxStep;
};


扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 **C+

+17**

如无特殊说明，本算法用**C++**实现。

文章标签：
云数据库 ClickHouse
算法
测试技术
C++
C#
闻缺陷则喜何志丹
目录
相关文章
TJUTCM-策士之九尾
|
人工智能 算法
【算法分析与设计】递归与分治策略（二）
【算法分析与设计】递归与分治策略
TJUTCM-策士之九尾
91 0
1897697198172439
|
6月前
|
算法 Python
深度优先算法
深度优先算法
1897697198172439
50 1
1897697198172439
|
6月前
|
算法 Python
广度优先算法
广度优先算法
1897697198172439
39 0
TJUTCM-策士之九尾
|
机器学习/深度学习 算法 编译器
【算法分析与设计】递归与分治策略（一）
【算法分析与设计】递归与分治策略
TJUTCM-策士之九尾
159 0
闻缺陷则喜何志丹
|
7月前
|
算法 测试技术 C#
【深度优化】【广度优先】【状态压缩】864. 获取所有钥匙的最短路径
【深度优化】【广度优先】【状态压缩】864. 获取所有钥匙的最短路径
闻缺陷则喜何志丹
40 0
Miss小远
|
算法
广度优先遍历（BFS）：逐层探索图的算法奥秘
在图论中，广度优先遍历（Breadth-First Search，BFS）是一种图遍历算法，它以一种逐层的方式探索图的节点。通过从起始节点开始，逐层向外扩展，BFS能够帮助我们解决许多与图相关的问题。
Miss小远
135 0
闻缺陷则喜何志丹
|
7月前
|
人工智能 算法 BI
【深度优先搜索】【C++算法】834 树中距离之和
【深度优先搜索】【C++算法】834 树中距离之和
闻缺陷则喜何志丹
57 1
诸葛子房
|
7月前
|
算法
树的深度优先和广度优先
树的深度优先和广度优先
诸葛子房
47 0
TJUTCM-策士之九尾
|
算法 搜索推荐 Windows
【算法分析与设计】递归与分治策略（三）
【算法分析与设计】递归与分治策略
TJUTCM-策士之九尾
88 0
梁同学golang算法
|
存储 人工智能 算法
图的遍历算法
图的遍历算法
梁同学golang算法
123 0

热门文章

最新文章

  • 1
    《Stata统计分析与应用（第2版）》一3.4 图形的保存、合并及修改
  • 2
    Maven 3.6.3 的下载、安装、配置、检测（详细讲解）
  • 3
    基于区块链的机器学习模型创建方案
  • 4
    WPF listview item mouse enter/over popup
  • 5
    DevExpress 10.2.4系列-ASPxListBox根据列值不同设置不同图标
  • 6
    [Spring]支持注解的Spring调度器
  • 7
    红帽7.4新增的安全特性
  • 8
    hdu 1800 Flying to the Mars
  • 9
    研究 flex 4 开发后台管理项目（1）
  • 10
    Error: XML response that was returned...
  • 1
    《docker高级篇（大厂进阶）：2.DockerFile解析》包括：是什么、DockerFile构建过程解析、DockerFile常用保留字指令、案例、小总结
    114
  • 2
    《Java 人工智能开发：Eclipse 与 IntelliJ IDEA 双雄助力》
    42
  • 3
    《Java 在开源 AI 框架中的中流砥柱角色》
    33
  • 4
    《Java 与大数据框架：AI 数据预处理的强力联盟》
    37
  • 5
    《Java 优化秘籍：计算密集型 AI 任务加速指南》
    33
  • 6
    《Java 与 OpenAI 协同：开启智能编程新范式》
    26
  • 7
    uniapp开发鸿蒙，是前端新出路吗？
    29
  • 8
    鸿蒙(HarmonyOS)原生AI能力之文本识别
    37
  • 9
    鸿蒙开发之PixelMap介绍与实现图片变换
    33
  • 10
    鸿蒙(HarmonyOS)开发之无须申请权限写入图片到相册
    39

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    【案例实战】SpringBoot整合阿里云文件上传OSS