做网站登录页面的论文,广州市行政区划图,蒙文网站建设情况汇报,装潢公司网站模板488. 祖玛游戏
你正在参与祖玛游戏的一个变种。
在这个祖玛游戏变体中#xff0c;桌面上有 一排 彩球#xff0c;每个球的颜色可能是#xff1a;红色 ‘R’、黄色 ‘Y’、蓝色 ‘B’、绿色 ‘G’ 或白色 ‘W’ 。你的手中也有一些彩球。
你的目标是 清空 桌面上所有的球。…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 161 hand.length 5board 和 hand 由字符 ‘R’、‘Y’、‘B’、‘G’ 和 ‘W’ 组成桌面上一开始的球中不会有三个及三个以上颜色相同且连着的球
解题思路
使用朴素的回溯法每次递归尝试向board的每一个位置插入hand里面的每一颗球插入以后检查是否能出现三个或者三个以上 且 颜色相同 的球相连的话并且把它们移除掉。
剪枝
使用set记录已经递归过的情况一旦当前递归的使用的球数小于了目前得出的最小球数
代码
class Solution {
public:int m0x3f3f3f3f;void dfs(int cnt,string hand,string board) {if (cntm) return;if (set.count({board,cnt}))return;set.insert({board,cnt});if (board.empty()) {mmin(m,cnt);return;}if (hand.empty()) return;for (int i 0; i board.size(); i) {for (int j 0; j hand.size(); j) {char curhand[j];hand.erase(hand.begin()j);string nsboard;ns.insert(ns.begin()i,cur);handler(ns);dfs(cnt1,hand,ns);hand.insert(hand.begin()j,cur);}}}int findMinStep(string board, string hand) {dfs(0,hand, board);return m0x3f3f3f3f ? -1 : m;}setpairstring,int set ;void handler(string s){int seq(1);for (int i 1; i s.size(); i) {if (is.size()s[i]s[i-1]) {seq;continue;}if(seq3){s.erase(i-seq,seq);i0;}seq1;}}};
