回忆一下祖玛游戏。现在桌上有一串球，颜色有红色(R)，黄色(Y)，蓝色(B)，绿色(G)，还有白色(W)。 现在你手里也有几个球。
每一次，你可以从手里的球选一个，然后把这个球插入到一串球中的某个位置上（包括最左端，最右端）。接着，如果有出现三个或者三个以上颜色相同的球相连的话，就把它们移除掉。重复这一步骤直到桌上所有的球都被移除。
找到插入并可以移除掉桌上所有球所需的最少的球数。如果不能移除桌上所有的球，输出 -1 。
示例:
输入: “WRRBBW”, “RB”
输出: -1
解释: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW （翻译者标注：手上球已经用完，桌上还剩两个球无法消除，返回-1）
输入: “WWRRBBWW”, “WRBRW”
输出: 2
解释: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty
输入:”G”, “GGGGG”
输出: 2
解释: G -> G[G] -> GG[G] -> empty
输入: “RBYYBBRRB”, “YRBGB”
输出: 3
解释: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty
标注:
你可以假设桌上一开始的球中，不会有三个及三个以上颜色相同且连着的球。
桌上的球不会超过20个，输入的数据中代表这些球的字符串的名字是 “board” 。
你手中的球不会超过5个，输入的数据中代表这些球的字符串的名字是 “hand”。
输入的两个字符串均为非空字符串，且只包含字符 ‘R’,’Y’,’B’,’G’,’W’。
解决
简单的深搜：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| class Solution
{
public:
string simplify(const string &s1, const string &s2)
{
int len1 = s1.size();
int len2 = s2.size();
if (len1 == 0) {
return s2;
}
if (len2 == 0) {
return s1;
}
if (s1[len1 - 1] == s2[0]) {
if (len1 > 1 && s1[len1 - 2] == s1[len1 - 1] && len2 > 1 && s2[0] == s2[1]) {
return simplify(s1.substr(0, len1 - 2), s2.substr(2, len2 - 2));
}
if (len1 > 1 && s1[len1 - 2] == s1[len1 - 1]) {
return simplify(s1.substr(0, len1 - 2), s2.substr(1, len2 - 1));
}
if (len2 > 1 && s2[0] == s2[1]) {
return simplify(s1.substr(0, len1 - 1), s2.substr(2, len2 - 2));
}
}
return s1 + s2;
}
int myMin(int a, int b) {
unsigned int ua = a, ub = b;
return int(ua < ub ? ua : ub);
}
int findMinStep(string board, string hand)
{
int len = board.size();
if (len == 0) {
return 0;
}
int handlen = hand.size();
if (handlen == 9) {
return -1;
}
set<char> ans;
int min_ans = -1;
for (int i = 0; i < handlen; i++)
{
char c = hand[i];
if (ans.count(c) == 0)
{
ans.insert(c);
for (int index = 0; index < len; index++)
{
if (board[index] == c)
{
string temp_ans = simplify(board.substr(0, index + 1), board.substr(index, len - index));
string temp_hand = hand.substr(0, i) + hand.substr(i + 1, handlen - i - 1);
int now_min = findMinStep(temp_ans, temp_hand) + 1;
if (now_min > 0) {
min_ans = myMin(now_min, min_ans);
}
if (index < len - 1 && board[index] == board[index + 1])
{
index++;
}
}
}
}
}
return min_ans;
}
};
|