提示: 欢迎访问OurACM平台。
Problem 1928 硬币翻转游戏

Accept: 34    Submit: 88
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Alice和Bob决定玩一种硬币翻转游戏。游戏的最初有n x m个硬币被放在一个棋盘上,有的正面朝上,有的反面朝上,当游戏开始的时候,他们轮流对硬币进行操作。

游戏的规则是这样的,当轮到一个人操作的时候,他必须挑选两枚硬币,将它们分别翻转(不是交换),同时这两枚硬币必须满足以下条件:

1. 两枚硬币必须在同一行或同一列

2. 两枚硬币中最右下的那枚必须是从正面翻转到反面

当一方无法做出满足上面要求的操作时,这一方就输了,游戏结束。

比如,当游戏初始状态是棋盘1时,Alice翻转完2枚硬币,可以将其变成 棋盘2的状态或棋盘3的状态。

Alice总是第一个操作,假设Alice和Bob都采取最优策略来玩这个游戏,请 你写一个程序判断Alice是否能赢。

Input

首先第一行为T,表示有T组数据。接下来为每组数据的结构:

每组测试数据的第一行有两个整数n和m (2 <= n, m <= 1000),代表棋盘上排列着n行m列的硬币,接下来n行,每行 m个字符描述硬币的初始状态,’F’代表硬币正面朝上,’B’代表硬币反面朝上。

Output

对于每组数据输出一行先输出组数(从1开始),接下来如果Alice能赢,输出YES,否则输出NO.

Sample Input

2 2 2 FB BB 2 2 BF BB

Sample Output

Case 1: NO Case 2: YES

Source

FOJ有奖月赛-2010年06月

Submit  Back  Status  Discuss