logo AlgoBeat OnlineJudge
登录 注册

#101434. [BZOJ 1434] [ZJOI2009]染色游戏

内存限制:64 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

一共 个硬币,摆成 的长方形。

dongdong 和 xixi 玩一个游戏,每次可以选择一个连通块,并把其中的硬币全部翻转,但是需要满足存在一个硬币属于这个连通块并且所有其他硬币都在它的左上方(可以正左方也可以正上方),并且这个硬币是从反面向上翻成正面向上。

dongdong 和 xixi 轮流操作,如果某一方无法操作,那么他就输了。

dongdong 先进行第一步操作,假设双方都采用最优策略,问 dongdong 是否有必胜策略。

输入格式

第一行一个数 ,表示他们一共玩 局游戏。

接下来是 组游戏描述。每组游戏第一行两个数 ,接下来 行每行 个字符,第 行第 个字符如果是 H 表示第 行第 列的硬币是正面向上,否则是反面向上。

列的左上方是指行不超过 并且列不超过 的区域。

输出格式

对于每局游戏,输出一行。

如果 dongdong 存在必胜策略则输出 - -,否则输出 = =

样例

样例输入 #1

32
3
HHH
HHH
2 3
HHH
TTH
2 1
T
H

样例输出 #1

= =
- -
- -

数据范围与提示

对于 的数据,满足

对于 的数据,满足