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

2024-01-13 07:36
文章标签 深度 游戏 优先 广度 剪枝 488 祖玛

本文主要是介绍【剪枝】【广度优先】【深度优先】488祖玛游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

【动态规划】458:可怜的小猪

涉及知识点

剪枝 广度优先 深度优先

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个W​ RRR − − − − − − − − > 连锁消除 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<pair<string, string>> 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<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;
}
}; ，

测试用例

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<pair<char, int>> 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++**实现。

这篇关于【剪枝】【广度优先】【深度优先】488祖玛游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/600685。

相关文章

hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
poj 3190 优先队列+贪心

poj 3190 优先队列+贪心

题意： 有n头牛，分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面，并且每个stall每次只能占用一头牛。 问最少需要多少个stall，并输出每头牛所在的stall。 e.g 样例： INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s
阅读更多...
poj 2431 poj 3253 优先队列的运用

poj 2431 poj 3253 优先队列的运用

poj 2431： 题意： 一条路起点为0， 终点为l。 卡车初始时在0点，并且有p升油，假设油箱无限大。 给n个加油站，每个加油站距离终点 l 距离为 x[i]，可以加的油量为fuel[i]。 问最少加几次油可以到达终点，若不能到达，输出-1。 解析： 《挑战程序设计竞赛》： “在卡车开往终点的途中，只有在加油站才可以加油。但是，如果认为“在到达加油站i时，就获得了一
阅读更多...
基于UE5和ROS2的激光雷达+深度RGBD相机小车的仿真指南(五)：Blender锥桶建模

基于UE5和ROS2的激光雷达+深度RGBD相机小车的仿真指南(五)：Blender锥桶建模

前言 本系列教程旨在使用UE5配置一个具备激光雷达+深度摄像机的仿真小车，并使用通过跨平台的方式进行ROS2和UE5仿真的通讯，达到小车自主导航的目的。本教程默认有ROS2导航及其gazebo仿真相关方面基础，Nav2相关的学习教程可以参考本人的其他博客Nav2代价地图实现和原理–Nav2源码解读之CostMap2D(上)-CSDN博客往期教程： 第一期：基于UE5和ROS2的激光雷达+深度RG
阅读更多...
韦季李输入法_输入法和鼠标的深度融合

韦季李输入法_输入法和鼠标的深度融合

在数字化输入的新纪元，传统键盘输入方式正悄然进化。以往，面对实体键盘，我们常需目光游离于屏幕与键盘之间，以确认指尖下的精准位置。而屏幕键盘虽直观可见，却常因占据屏幕空间，迫使我们在操作与视野间做出妥协，频繁调整布局以兼顾输入与界面浏览。 幸而，韦季李输入法的横空出世，彻底颠覆了这一现状。它不仅对输入界面进行了革命性的重构，更巧妙地将鼠标这一传统外设融入其中，开创了一种前所未有的交互体验。 想象
阅读更多...
国产游戏崛起：技术革新与文化自信的双重推动

国产游戏崛起：技术革新与文化自信的双重推动

近年来，国产游戏行业发展迅猛，技术水平和作品质量均得到了显著提升。特别是以《黑神话：悟空》为代表的一系列优秀作品，成功打破了过去中国游戏市场以手游和网游为主的局限，向全球玩家展示了中国在单机游戏领域的实力与潜力。随着中国开发者在画面渲染、物理引擎、AI 技术和服务器架构等方面取得了显著进展，国产游戏正逐步赢得国际市场的认可。然而，面对全球游戏行业的激烈竞争，国产游戏技术依然面临诸多挑战，未来的
阅读更多...
hdu1010 奇偶剪枝

hdu1010 奇偶剪枝

恰好t时间到达 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.Arrays;import
阅读更多...
POJ2010 贪心优先队列

POJ2010 贪心优先队列

c头牛,需要选n头（奇数）；学校总共有f的资金， 每头牛分数score和学费cost，问合法招生方案中,中间分数（即排名第(n+1)/2）最高的是多少。 n头牛按照先score后cost从小到大排序； 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi
阅读更多...
免费也能高质量！2024年免费录屏软件深度对比评测

免费也能高质量！2024年免费录屏软件深度对比评测

我公司因为客户覆盖面广的原因经常会开远程会议，有时候说的内容比较广需要引用多份的数据，我记录起来有一定难度，所以一般都用录屏工具来记录会议内容。这次我们来一起探索有什么免费录屏工具可以提高我们的工作效率吧。 1.福晰录屏大师 链接直达：https://www.foxitsoftware.cn/REC/  录屏软件录屏功能就是本职，这款录屏工具在录屏模式上提供了多种选项，可以选择屏幕录制、窗口
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2