0488：祖玛游戏（★★）

Ian

2016-05-02 约 1230 字预计阅读 3 分钟次阅读

力扣第 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' 组成
桌面上一开始的球中，不会有三个及三个以上颜色相同且连着的球

分析

考虑 bfs 并剪枝
假设要将 h[j] 插入 b[i-1] 和 b[i] 之间，考虑哪些情况是有效的
- h[j]=b[i]，有效
- h[j]=b[i-1]，这和插入 b[i-2] 和 b[i-1] 之间没区别，可以不考虑
- b[i]=b[i-1]，有效
  - 例如桌面上的球为 ‘RRWWRRBBRR’，手中的球为 ‘WB’
  - 操作方法：RRWWRRBBRR→RRWWRRBBR(W)R→RRWWRR(B)BBRWR→’'
- 全都不相等，可以不考虑
  - 假如某个成功方案是插入 h[j] 到位置 i，最终和前面/后面某个位置的球 x 一起消除
  - 直接将 h[j] 插入到球 x 旁边，不会影响 h[j],b[i-1],b[i] 的消除过程，依然是成功方案

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        @cache
        def clean(s):
            n = 1
            while n:
                s,n = re.subn(r'(.)\1{2,}','',s) 
            return s
        hand = ''.join(sorted(hand))
        Q = deque([(0,board,hand)])
        vis = {(board,hand)}
        while Q:
            w,b,h = Q.popleft()
            for i,j in product(range(len(b)),range(len(h))):
                if h[j]==b[i] or (i and b[i-1]==b[i]):
                    b2 = clean(b[:i]+h[j]+b[i:])
                    h2 = h[:j]+h[j+1:]
                    if not b2:
                        return w+1
                    if (b2,h2) not in vis:
                        vis.add((b2,h2))
                        Q.append((w+1,b2,h2))
        return -1

711 ms

目录

0488：祖玛游戏（★★）

题目

分析

解答