唯拓网站建设,网站建设公司营业执照图片,无锡谷歌推广,销售型企业有哪些公司题目描述
小 Q 是一个非常聪明的孩子#xff0c;除了国际象棋#xff0c;他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个 nn 黑白方阵进行#xff08;如同国际象棋一般#xff0c;只是颜色是随意的#xff09;。每次可以对该矩阵进行两种操作#xff1a;
行…题目描述
小 Q 是一个非常聪明的孩子除了国际象棋他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个 n×n 黑白方阵进行如同国际象棋一般只是颜色是随意的。每次可以对该矩阵进行两种操作
行交换操作选择矩阵的任意两行交换这两行即交换对应格子的颜色。列交换操作选择矩阵的任意两列交换这两列即交换对应格子的颜色。
游戏的目标即通过若干次操作使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。
对于某些关卡小 Q 百思不得其解以致他开始怀疑这些关卡是不是根本就是无解的于是小 Q 决定写一个程序来判断这些关卡是否有解。
输入格式
本题单测试点内有多组数据。
第一行包含一个整数 T表示数据的组数对于每组数据输入格式如下
第一行为一个整数代表方阵的大小 n。 接下来 n 行每行 n 个非零即一的整数代表该方阵。其中 0 表示白色1 表示黑色。
输出格式
对于每组数据输出一行一个字符串若关卡有解则输出 Yes否则输出 No。
输入输出样例 解题思路
匈牙利二分图匹配
AC代码
#include bits/stdc.h
using namespace std;
int n,m,T,ans,x,vis[200010],A[200010];
vectorint g[200010];
bool find(int x);
int main ( )
{cinT;while(T--){cinn;ans0;for(int i1;in;i)g[i].clear(),A[i] 0;for(int i1;in;i)for(int j1;jn;j){scanf(%d,x);if(x)g[i].push_back(j);}for(int i 1 ; i n ;i){memset(vis , 0 ,sizeof(vis));ans find(i);}puts(ansn?Yes:No);}
}bool find(int x)
{for(int i0;ig[x].size();i){if(!vis[g[x][i]]){vis[g[x][i]] 1;if(!A[g[x][i]] || find(A[g[x][i]])){A[g[x][i]]x;return 1;}}}return 0;
}
