Description
一共n × m 个硬币，摆成n × m 的长方形。dongdong 和xixi 玩一个游戏， 每次可以选择一个连通块，并把其中的硬币全部翻转，但是需要满足存在一个 硬币属于这个连通块并且所有其他硬币都在它的左上方(可以正左方也可以正 上方)，并且这个硬币是从反面向上翻成正面向上。dongdong 和xixi 轮流操作。 如果某一方无法操作，那么他(她) 就输了。dongdong 先进行第一步操作，假 设双方都采用最优策略。问dongdong 是否有必胜策略。
Input
第一行一个数T，表示他们一共玩T 局游戏。接下来是T 组游戏描述。每 组游戏第一行两个数n;m，接下来n 行每行m 个字符，第i 行第j 个字符如 果是“H” 表示第i 行第j 列的硬币是正面向上，否则是反面向上。第i 行j 列 的左上方是指行不超过i 并且列不超过j 的区域。
Output
对于每局游戏，输出一行。如果dongdong 存在必胜策略则输出“- -”(不含 引号) 否则输出“= =”(不含引号)。(注意输出的都是半角符号，即三个符号 ASCII 码分别为45,61,95)
Sample Input
32
3
HHH
HHH
2 3
HHH
TTH
2 1
T
H
3
HHH
HHH
2 3
HHH
TTH
2 1
T
H
Sample Output
= =
- -
- -
- -
- -
HINT
对于40% 的数据，满足1 ≤ n;m ≤ 5。
对于100% 的数据，满足1 ≤ n;m ≤ 100，1 ≤ T ≤ 50。
先考虑一维
SG[i]为单独考虑只有i是反面，其他都是正面的SG值，这样原情况可以转化为很多子游戏
假设要求SG[3]
也就是001
有这么几种：000 010 110
SG[3]=mex{0,2,2^1}=1
SG(4) = mex{0, 1, 1 XOR 2, 1 XOR 2 XOR 1} = 4；
SG(5) = mex(0, 4, 4 XOR 1, 4 XOR 1 XOR 2, 4 XOR 1 XOR 2 XOR 1) = 1；
枚举了很多SG发现SG[n]=lowbit(n)
将类似的方法拓展到2维：
要求SG[2][2],也就是
归纳得出，在i,j都大于1时，SG[i][j]=2i+j-2
在i或j为0时，为一维的算法
优于2200过大，所以用二进制存储
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct Num
{
int a[];
}SG[][],ans;
int n,m,flag;
char s[];
Num operator ^(const Num &A,const Num &B)
{int i;
Num C;
memset(C.a,,sizeof(C.a));
for (i=;i<=;i++)
if (A.a[i]!=B.a[i]) C.a[i]=;
return C;
}
int lowbit(int x)
{
return x&(-x);
}
void getSG()
{int i,j;
SG[][].a[]=;
for (i=;i<=;i++)
{
int x=lowbit(i);
for (j=;j<=;j++)
if ((<<j)==x)
SG[][i].a[j]=SG[i][].a[j]=;
}
for (i=;i<=;i++)
{
for (j=;j<=;j++)
{
SG[i][j].a[i+j-]=;
}
}
}
int main()
{int T,i,j;
cin>>T;
getSG();
while (T--)
{
cin>>n>>m;
memset(ans.a,,sizeof(ans.a));
for (i=;i<=n;i++)
{
scanf("%s",s+);
for (j=;j<=m;j++)
{
if (s[j]=='T') ans=ans^SG[i][j];
}
}
flag=;
for (i=;i<=;i++)
if (ans.a[i])
{flag=;break;}
if (flag) printf("-_-\n");
else printf("=_=\n");
}
}