1652. [POJ2931][MIT2005]拖延游戏

【题目描述】

在很久很久以前，有两名研究生是好朋友。在搞研究的短暂空闲（通常不超过几小时）中，他们喜欢玩拖延游戏。

拖延游戏有两名玩家（分成黑和白），玩家轮流移动。游戏是从塔上移除立方体。每个立方体都是黑色或白色的。最初有4座塔，每座塔都是由立方体组成的一个栈。当轮到某名玩家时，他可以移除他的颜色相同的任意立方体（白色玩家只能移除白色立方体，黑色玩家只能移除黑色立方体）。并且该立方体上方的立方体也会被移除，无论它们的颜色是什么。例如，假设由如下立方体（从下到上）组成的一座塔：黑，白，黑，白。那么，如果黑色玩家移除了最底部的黑色立方体，他就移除了整座塔。黑色玩家也可以移除第三个立方体，则同时就移除了第四个立方体。如果白色玩家移除了第二个立方体，整座塔就只剩下一个黑色立方体了。白色玩家也可以移除第四个立方体。如果一名玩家无法移除任何立方体，他就输了。

由于在大学期间学习了这个游戏的复杂之处，两名研究生知道如何完美地玩这个游戏，也就是说，如果一名玩家有必胜策略，那么这名玩家就一定会赢。但有时候，他们发现了一点：对于大多数初始状态，一名玩家总是有必胜策略，无论谁先移动。他们把初始状态称为W-状态，如果无论谁先移动，白色玩家总是有必胜策略。如果黑色玩家总有必胜策略，则称其为B-状态。

除此之外，他们注意到一些局部状态至少和别的（局部）状态一样对某一名玩家有利。一个局部状态C定义为3座塔的集合，注意到局部状态C加上第四座塔T就是一完整的游戏状态，我们把它记作(C,T)。对于上述“至少和别的状态一样有利”我们正式定义如下。一个局部状态C1（由3座塔组成）至少和局部状态C2（同样包含3座塔）一样对白色玩家有利，当且仅当对于任意的第四座塔T，如果(C2,T)是W-状态那么(C1,T)也是W-状态。换句话说，不存在第四座塔T使得(C1,T)不是W-状态而且(C2,T)是W-状态。

给出两个局部状态C1和C2，你将要判断C1是否至少和C2一样对白色玩家有利。

【输入格式】

输入文件的第一行有一个整数，代表数据组数。

每组数据的格式如下：

第一行形如"Test N"，其中N是这组数据的编号。

接下来有8行，按如下格式描述了两个局部状态C1和C2：

局部状态的第一行有三个整数n1,n2,n3，代表这个局部状态中三座塔的高度（0<=n1,n2,n3<=50）。

第二行有n1个空格隔开的字母（B或W），描述了第一座塔。

第三行有n2个空格隔开的字母，描述了第二座塔。

第四行有n3个空格隔开的字母，描述了第三座塔。

字母W代表一个白色立方体，字母B代表黑色立方体。每座塔都按照从下到上的顺序描述。

【输出格式】

对每组数据，输出单独的一行，包含数据编号和Yes（如果C1至少和C2一样对白色有利）或No（其他情况）。

【样例输入】

2

Test 1

3 3 1

W B B

W B W

B

3 3 3

B W W

B W W

W B B

Test 2

3 3 2

W B B

W B W

B B

3 3 3

B W W

B W W

W B B

【样例输出】

Test 1: Yes

Test 2: No

【提示】

数据组数<=10

【来源】

POJ 2931 Procrastination

MIT Programming Contest 2005