会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员，或
购买
该题目所属题库
，可解锁完整内容。
思路：搜索+剪枝
原题详见祖玛游戏
#include <bits/stdc++.h>
using namespace std;
// 哈希表，用于记忆化搜索，避免重复计算
P1890.2024.08.14-第四题-消消乐
题目描述
小友在部门团建中参与了一款消消乐游戏，该游戏规则如下:
- 桌子上有一排动物图案，分别是猫"C"，狗"D"，狮子"L"，猴子"M"，鸟"B"。
- 小友的手里有一些对应的动物图案，小友的日标是清空桌子上的所有图案
- 每一回合，从小友手中的图案中任选一个，插入桌子的图案中，可以插入在两个图案之间或一排图案的两端
- 在插入图案之后，如果有出现三个或者三个以上图案相同且相连的情况，则将他们移除
- 如果移除图案后，再次出现三个或者三个以上图案相同且相连的情况，则可以继续移除这些图案，直到不再满条件
- 如果桌面上的图案均被移除，则认为小友获得了胜利
- 重复上述过程，直至图案全被移除或小友手中没有图案
给定两个字符串，分别表示桌面上初始图案排布情况和小友手里的图案，请你帮小友计算如果按照上还步骤移除桌面上所有的图案，所需要最少的图享数量，如果无法移除所有的图案，则返回-1
输入描述
输入共有两行
第一行表示桌面上初始图案分布排列情况
第二行表示小友手中图案情况
字符串均由“C”、“D”、“L”、“M”、“B”组成
输出描述
输出需要移除桌面上所有图案所需要最少的图案数量，若无法移除，则返回-1
样例
输入
BBCCLLBB
BCLCB
输出
2
