488. 祖玛游戏¶

难度：困难

题目¶

回忆一下祖玛游戏。现在桌上有一串球，颜色有红色(R)，黄色(Y)，蓝色(B)，绿色(G)，还有白色(W)。现在你手里也有几个球。

每一次，你可以从手里的球选一个，然后把这个球插入到一串球中的某个位置上（包括最左端，最右端）。接着，如果有出现三个或者三个以上颜色相同的球相连的话，就把它们移除掉。重复这一步骤直到桌上所有的球都被移除。

找到插入并可以移除掉桌上所有球所需的最少的球数。如果不能移除桌上所有的球，输出 -1 。

示例 1：

输入：board = "WRRBBW", hand = "RB"
输出：-1
解释：WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW

示例 2：

输入：board = "WWRRBBWW", hand = "WRBRW"
输出：2
解释：WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty

示例 3：

输入：board = "G", hand = "GGGGG"
输出：2
解释：G -> G[G] -> GG[G] -> empty

示例 4：

输入：board = "RBYYBBRRB", hand = "YRBGB"
输出：3
解释：RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty

提示：

你可以假设桌上一开始的球中，不会有三个及三个以上颜色相同且连着的球。
1 <= board.length <= 16
1 <= hand.length <= 5
输入的两个字符串均为非空字符串，且只包含字符 'R','Y','B','G','W'。

Reference

题解¶

定义当前游戏的状态，一个状态由桌上的球列表与手中的球列表表示。每次插入操作构成一个状态间的状态转移过程。使用两个队列存储当前状态，和当前状态的所有可能转移到的状态。再将转移到的状态设为当前状态，继续进行搜索过程。本题中，状态转移是单向的，因此不需要考虑重复经过一种状态的情况。

由于一个状态可以转换为更多的状态，需要在这些状态间进行筛选。筛选规则如下：

当插入位置两侧的颜色不同时，新球的颜色需要与左右两侧其中一个球的颜色相同
当插入位置两侧颜色相同时，新球可以使用任意可能的颜色
当插入位置位于端点时，新球的颜色需要与相邻球的颜色相同

如上剪枝思路不会影响测例"RRYGGYYRRYGGYYRR" "GGBBB"与"RRWWRRBBRR" "WB"等需要将连续序列分割的情况。不满足如上条件的状态视为无效的状态，直接跳过对这些状态的搜索。

使用链表模拟队列，每个链表节点表示问题的一个状态，由于链表节点需要多次分配，可以使用提前分配内存池的策略以减少malloc()的调用次数。

struct Queue
{
    char *val;
    int colorsOnHand[5];
    struct Queue *next;
};

struct Queue *nodePool;
int poolSize;
int poolAllocated;

struct Queue *getNode(char *val, struct Queue *next, int *colorsOnHand)
{
    int i = 0;
    struct Queue *ret;
    if (!nodePool || poolAllocated >= poolSize)
    {
        if (poolAllocated)
            poolSize <<= 1;
        else
            poolSize = 1000;
        poolAllocated = 0;
        nodePool = (struct Queue *)malloc(sizeof(struct Queue) * poolSize);
    }
    ret = nodePool + (poolAllocated++);
    ret->val = val;
    ret->next = next;
    for (i = 0; i < 5; i++)
        ret->colorsOnHand[i] = colorsOnHand[i];
    return ret;
}

分两步进行状态转移，第一步先插入一个球，第二步消除连续的球，直到无球可消。

char *strPool;
int strSize;
int strAllocated;

char *getStr(int len)
{
    if (!strPool || strAllocated + len >= strSize)
    {
        if (strAllocated)
            strSize <<= 1;
        else
            strSize = 32768;
        strAllocated = 0;
        strPool = (char *)malloc(sizeof(char) * strSize);
    }
    char *ret = strPool + strAllocated;
    strAllocated += len;
    return ret;
}

bool play(char *src)
{
    char *ptrfast = src, *ptrslow = src, cur = 0;
    int i = 0;
    bool flag = false;
    while (*ptrfast)
    {
        if (cur == *ptrfast)
            i++;
        else
        {
            if (i < 3)
            {
                while (i)
                {
                    *(ptrslow++) = cur;
                    i--;
                }
            }
            else
                flag = true;
            i = 1;
            cur = *ptrfast;
        }
        ptrfast++;
    }
    if (i < 3)
    {
        while (i)
        {
            *(ptrslow++) = cur;
            i--;
        }
    }
    else
        flag = true;
    *ptrslow = 0;
    return flag;
}

char *addBall(char *src, int len, char ball, int loc)
{
    char *ret = (char *)malloc(sizeof(char) * (len + 2));
    ret[len + 1] = 0;
    memcpy(ret, src, sizeof(char) * loc);
    memcpy(ret + loc + 1, src + loc, sizeof(char) * (len - loc));
    ret[loc] = ball;
    return ret;
}

int findMinStep(char * board, char * hand) {
    struct Queue *current = NULL, *temp = NULL;
    char *cur = hand, *init = getStr(strlen(board) + 1), *newseq = NULL,
         *colors = "RYBGW";
    int i = 0, j = 0, len = 0, ret = 0, colorsOnHand[5] = {0}, flag;

    nodePool = NULL;
    poolSize = 0;
    poolAllocated = 0;
    strPool = NULL;
    strSize = 0;
    strAllocated = 0;

    strcpy(init, board);
    do
        for (i = 0; i < 5; i++)
            if (*cur == colors[i])
                colorsOnHand[i]++;
    while (*(++cur));

    current = getNode(init, NULL, colorsOnHand);
    while (current)
    {
        while (current)
        {
            len = strlen(current->val);
            if (!len)
                return ret;
            for (i = 0; i <= len; i++)
            {
                flag = false;
                for (j = 0; j < 5; j++)
                {
                    if (current->colorsOnHand[j] == 0)
                        continue;
                    if (i > 0)
                        flag = flag || current->val[i - 1] == colors[j];
                    if (i < len)
                        flag = flag || current->val[i] == colors[j];
                    if (i > 0 && i < len)
                        flag = flag || current->val[i - 1] == current->val[i];
                    if (!flag)
                        continue;
                    current->colorsOnHand[j]--;
                    newseq = addBall(current->val, len, colors[j], i);
                    while (play(newseq));
                    temp = getNode(newseq, temp, current->colorsOnHand);
                    current->colorsOnHand[j]++;
                }
            }
            current = current->next;
        }
        ret++;
        current = temp;
        temp = NULL;
    }
    return -1;
}

488. 祖玛游戏¶

题目¶

题解¶

评论