#PQJ2372x13823. QOJ 2372_13823
QOJ 2372_13823
2007 年浙江省省选第一试
2007-4-7
- 6 - 矩阵游戏 【问题描述】
小Q 是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游 戏——矩阵游戏。矩阵游戏在一个N*N 黑白方阵进行(如同国际象棋一般,只 是颜色是随意的)。每次可以对该矩阵进行两种操作: l 行交换操作:选择矩阵的任意两行,交换这两行(即交换对应格子的 颜色) l 列交换操作:选择矩阵的任意行列,交换这两列(即交换对应格子的 颜色)
游戏的目标,即通过若干次操作,使得方阵的主对角线(左上角到右下角的连 线)上的格子均为黑色。
对于某些关卡,小Q 百思不得其解,以致他开始怀疑这些关卡是不是根本就 是无解的!!于是小Q 决定写一个程序来判断这些关卡是否有解。 【输入文件】
输入文件matrix.in 第一行包含一个整数T,表示数据的组数。
接下来包含T 组数据,每组数据第一行为一个整数N,表示方阵的大小;接 下来N 行为一个N*N 的01 矩阵(0 表示白色,1 表示黑色)。 【输出文件】
输出文件应包含T 行。对于每一组数据,如果该关卡有解,输出一行Yes; 否则输出一行No。 【样例输入】
2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0
2007 年浙江省省选第一试
2007-4-7
- 7 - 【样例输出】
No
Yes 【数据规模】
对于20%的数据,N ≤ 7
对于50%的数据,N ≤ 50
对于100%的数据,N ≤ 200