0488. Zuma Game
===============
题目信息
--------
:题号: 0488
:难度: Hard
:主题: 彩球序列、手中球、插入操作、连续消除
:原题: `LeetCode 0488 `_
:重点: 每次插入一颗手中球、三个及以上同色连续球立即消除、消除可连锁、返回清空棋盘的最少插入数
题目重述
--------
给定棋盘彩球字符串 ``board`` 和手中彩球字符串 ``hand``,颜色只可能是 ``R``、``Y``、``B``、``G``、``W``。一次操作从手中选择一颗尚未使用的球,插入棋盘任意位置。
每次插入后,棋盘中任意长度至少为 3 的连续同色球组会立即消除;消除后两侧连接可能形成新的同色组,需要继续连锁消除,直到不存在可消除组。返回清空整个棋盘所需的最少插入次数;若使用手中球仍无法清空,返回 ``-1``。
``board.length`` 位于 ``[1, 16]``,``hand.length`` 位于 ``[1, 5]``。初始棋盘中不存在长度至少为 3 的连续同色组。每颗手中球最多使用一次。
自建示例
--------
插入一颗球立即清空:
.. code-block:: text
输入:board = "RR",hand = "R"
输出:1
解释:把手中的 R 插在两个 R 旁边形成 RRR,三个球立即全部消除,棋盘清空。
手中颜色无法形成消除:
.. code-block:: text
输入:board = "R",hand = "G"
输出:-1
解释:插入唯一的 G 后仍没有三个连续同色球,且手中已无其他球,无法清空棋盘。
规范化消除后的棋盘并记忆化搜索
------------------------------
一次插入后,先把所有长度至少为 3 的连续同色段消除;删除后新连接的两段可能再次达到 3 个,因此 ``shrink`` 需要递归处理,直到棋盘稳定。搜索状态由稳定后的棋盘和手中五种颜色的剩余数量共同决定。
在每个状态中尝试把一种仍有库存的颜色插入每个位置,消除并递归求剩余最少步数。相同的“棋盘 + 手中库存”只需计算一次;手中最多 5 颗球,因此用 6 表示无解即可与合法答案区分。
C++ 实现
--------
.. code-block:: cpp
class Solution {
const std::string colors = "RYBGW";
std::unordered_map memo;
std::string shrink(const std::string& board) {
for (int begin = 0;
begin < static_cast(board.size());) {
int end = begin + 1;
while (end < static_cast(board.size()) &&
board[end] == board[begin]) {
++end;
}
if (end - begin >= 3) {
return shrink(board.substr(0, begin) +
board.substr(end));
}
begin = end;
}
return board;
}
std::string makeKey(const std::string& board,
const std::array& hand) {
std::string key = board + '|';
for (int count : hand) key.push_back(static_cast('0' + count));
return key;
}
int search(const std::string& rawBoard,
std::array& hand) {
std::string board = shrink(rawBoard);
if (board.empty()) return 0;
std::string key = makeKey(board, hand);
auto it = memo.find(key);
if (it != memo.end()) return it->second;
int best = 6;
for (int position = 0;
position <= static_cast(board.size()); ++position) {
for (int color = 0; color < 5; ++color) {
if (hand[color] == 0) continue;
--hand[color];
std::string next = board.substr(0, position) +
colors[color] + board.substr(position);
best = std::min(best, 1 + search(next, hand));
++hand[color];
}
}
memo[key] = best;
return best;
}
public:
int findMinStep(std::string board, std::string handString) {
std::array hand{};
for (char character : handString) {
++hand[colors.find(character)];
}
memo.clear();
int answer = search(board, hand);
return answer >= 6 ? -1 : answer;
}
};
代码分析
--------
``shrink`` 每次消除后重新从头检查,保证连锁反应完整;记忆化键包含库存数量,所以相同棋盘但可用颜色不同的状态不会错误合并。回溯最多使用 5 颗手中球,最坏状态数呈指数增长,单个状态还需尝试插入位置和颜色;额外空间主要为状态缓存和递归栈。