问题 4541 --(2008校内赛) ZUMA

4541: (2008校内赛) ZUMA

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

小Y同学十分喜欢玩一款叫做ZUMA的游戏。这个游戏中有各种各样彩色的球,顺序的滚动。小Y操纵青蛙,吐出球插入到序列的某个位置。如果吐出的球在插入后,相邻共有两个或者两个以上的彩球颜色一样的话(即同色有至少三个球连在一起),则同色彩球消掉。更激动人心的是,有时候还可能出现连消的情况,因为彩球消掉后,原来在彩球两端的球合并到了一起,如果合并处出现了三个或者三个以上同色彩球的话,则可以继续消掉,运气好的时候,可能可以连消很多次。现在给出彩球的序列,以及小Y某次射出彩球的颜色以及位置,问消除后,剩下多少个彩球(假设没有增加新的彩球)。

输入

有多组测试数据。输入第一行为一个正整数C,代表随后有C组数据。然后每组数据首先输入一个无空格的字符串,最长可能包括10000个字符,为目前的彩球分布情况。字符串全由大写字母组成,相同的字母代表相同颜色的球。然后输入一个正整数p,其数值小于字符串长度,说明小Y的球打在了第p个球与第p+1个球之间(不会打在所有球的最前面或者最后面)。最后是一个字符,代表打出球的颜色,也为大写。

输出

对应每组测试数据,输出一行,该行有一个整数,为剩下彩球的个数。

样例输入

5<br/>AAAAABBBCC 4 B<br/>CDABBAADCCCC 3 B <br/>AAAABBCCCC 5 B<br/>AACBBCCA 3 B<br/>AAABB 4 B<br/>

样例输出

11<br/>7<br/>8<br/>0<br/>3<br/>

提示

说明:第一组数据不能消除,加上新射入的B,一共剩下11个彩球。第二组数据首先B被消除,然后A也连续消除,剩下7个彩球。注意虽然C也有4个,但是由于不是在合并处,因此不能消除。

来源

[提交][状态]