LeetCode 488. 祖玛游戏

题目描述

你有一个祖玛游戏：一条轨道上有一串彩色球（用字符串 board 表示），你手里有另外一些球（用字符串 hand 表示）。游戏规则是：

• 每次你可以从 hand 中选一个球，插入到 board 的任意位置。
• 如果插入后，存在三个或更多相同颜色的球连在一起，它们就会消失，并且左右两边的球会靠拢；如果靠拢后再次形成三个或以上连续同色球，会继续消除（连锁反应）。
• 目标是用最少的步数（每次插入一个球算一步）让 board 清空。如果无法清空，返回 -1。

示例

board = "WRRBBW", hand = "RB"
输出: -1
解释：无法清空轨道上的球。

board = "WWRRBBWW", hand = "WRBRW"
输出: 2
解释：一种方案：WWRRBBWW → WWRRRBBWW → WWBBWW → WWWW → 空

解题思路

这是一个状态搜索问题，适合用 BFS 或 DFS+剪枝 求解。因为要求最少步数，BFS 更直观（首次到达空棋盘即最优解）。
难点在于：

1. 插入球的位置很多（board.length()+1 个位置）。
2. 插入后可能触发连锁消除，需要模拟消除过程。
3. 需要避免重复状态（相同棋盘 + 相同手持球集合视为同一状态）。

步骤详解

第 1 步：状态表示

将当前棋盘状态和手持球的状态作为一个整体状态。

• 棋盘用字符串 board 表示。
• 手持球用字符串 hand 表示（注意：手持球的顺序不重要，可以用排序或计数来去重）。
  为了去重，我们可以用 (board, hand) 作为状态，但 hand 最好按字符排序存储，避免因顺序不同重复访问。

第 2 步：模拟消除过程

写一个函数 eliminate(board)：

• 用类似栈的方法扫描字符串，检测连续相同字符长度 ≥ 3 的区间并删除，重复直到不能消除。
  具体做法：

1. 初始化栈（或直接遍历+双指针模拟）。
2. 遍历 board，逐个字符检查：
   • 如果当前字符与栈顶字符相同，继续压栈。
   • 否则，检查栈中刚积累的相同字符长度是否 ≥ 3，如果是，弹出这些字符，然后继续处理。
   • 注意：消除后当前字符可能与新栈顶相同，所以要小心处理。
3. 更简单的方法：循环扫描，每次找出所有连续 ≥ 3 的区间，一次性删除，然后重新拼接字符串，重复直到没有可消除的区间。

示例：
"WWRRBBWW" 插入 'R' 后成 "WWRRRBBWW"

• 扫描到 "RRR" 消除 → "WWBBWW"
• 扫描到 "BB" 不够 3 个，"WW" 也不够 3 个，停止。

第 3 步：BFS 框架

1. 初始状态：(board, hand)。
2. 队列中存储 (board, hand, step)，但 step 可以从 BFS 层数获得。
3. 对于每个状态，枚举手持球中的每个球（去重：如果连续相同球，只试第一个避免重复），再枚举插入到棋盘的所有位置（去重：如果插入位置前后字符相同，只插在连续相同块的第一个位置后面？这里可以剪枝，但简单起见先枚举所有位置）。
4. 插入后调用 eliminate 得到新棋盘。
5. 如果新棋盘为空，返回 step+1。
6. 如果新棋盘非空，且手持球还有剩余，将新状态 (newBoard, newHand) 加入队列（去重检查）。
7. 用 visited 集合记录已访问的 (board, hand) 状态。

第 4 步：剪枝优化

• 手持球中某个颜色在棋盘上不存在，且不是用于消除的，则不能直接帮助消除，但可能连锁消除中间部分，所以不能直接剪掉。
• 更有效的剪枝：如果手持球颜色与棋盘上相邻颜色不同，且无法与相邻球形成 ≥ 3 的连续，则插入无效？但连锁消除可能后续发生，所以不能简单判断。
• 主要靠 BFS 层数保证最少步数，状态去重避免重复扩展。

第 5 步：代码结构（伪代码）

function findMinStep(board, hand):
    对手持球排序（用于去重）
    visited = set()
    queue = deque([(board, hand)])
    steps = 0
    while queue:
        for 当前层大小:
            cur_board, cur_hand = queue.popleft()
            for 每个手持球颜色（去重）:
                for 每个插入位置 in [0, len(cur_board)]:
                    new_board = insert(cur_board, pos, color)
                    new_board = eliminate(new_board)  # 连锁消除
                    if new_board 为空: return steps+1
                    new_hand = remove color from cur_hand
                    if (new_board, new_hand) 未访问:
                        visited.add(...)
                        queue.append((new_board, new_hand))
        steps++
    return -1

关键点总结

1. BFS 保证最短路径。
2. 状态去重：(board, hand) 的规范化表示（hand 排序）。
3. 消除模拟：要正确实现连锁消除，可用循环扫描直到不变。
4. 效率：棋盘长度 ≤ 20，手持球长度 ≤ 5，状态数可能很大，但去重后可控。

通过以上步骤，你可以逐步实现这个经典的搜索题目，理解 BFS 在游戏类问题中的应用。