#PQJ2372x13823. QOJ 2372_13823

    ID: 2799 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:ZJOI 2007枚举

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