Sgu229 Divide and conquer

时间限制:5s      空间限制:64MB

题目描述

You are to write a program which will divide set Q of squares into two parts, in such a way that one of them can be presented as other after rotations on 90 degrees and shifts along some vector. Set Q is the subset of NxN square. 对于1*1的骨牌 判断这些放在棋盘里的骨牌能否划分成两个完全相等的部分。 这里规定,“完全相等”是指划分成两部分中的任一部分可以通过旋转一个整90度(0,90,180或270度 )之后,再经过一些杂乱的平移后使两部分完全重合。这里定义旋转90度可以看作,将整个棋盘旋转90度得到的骨牌的新位置就是这个骨牌原来的位置旋转90度后的位子。 例如 左图的骨牌通过整体顺时针旋转90度后可以得到 110 001 010 111 010 000


输入格式

第一行,一个整数T(T≤20),表示数据组数。 每组数据第一行一个整数N(N≤20),表示一个N*N的棋盘。 下面接N行01串,表示骨牌的摆放情况,1表示有骨牌,0表示没有骨牌。


输出格式

输出有T行,如果可以将骨牌分成“完全相等”的两部分,则输出“YES”,否则输出“No”表示不可以。


样例输入

2                           
3                            
100
110
010
3
000
010
000

样例输出

YES
No

提示

N≤20


题目来源

没有写明来源