Given an N*N matrix with each entry equal to 0 or 1. You can swap any two rows or any two columns. Can you find a way to make all the diagonal entries equal to 1?
InputThere are several test cases in the input. The first line of each test case is an integer N (1 <= N <= 100). Then N lines follow, each contains N numbers (0 or 1), separating by space, indicating the N*N matrix.OutputFor each test case, the first line contain the number of swaps M. Then M lines follow, whose format is “R a b” or “C a b”, indicating swapping the row a and row b, or swapping the column a and column b. (1 <= a, b <= N). Any correct answer will be accepted, but M should be more than 1000.
If it is impossible to make all the diagonal entries equal to 1, output only one one containing “-1”.
Sample Input
2
0 1
1 0
2
1 0
1 0
Sample Output
1
R 1 2
-1 题意：给你一个n*n的棋盘，值都是0或1，你可以任意交换两行两列，不要求最少步数，交换的结果让对角线都为1 思路：首先我们可以看出如果可以交换出结果，只依靠行交换或者列交换即可，然后我们要求的是一条对角线，意思是每列匹配的位置必须是固定的行，
我们把行当做二分图的左边，列当做二分图的右边，1的时候就是行和列直接有一条边，
-1问题我们直接用匈牙利算法求出，求出最大匹配是否是n，如果不是的话，说明有些行还没有匹配，所以不符合要求，如果最大匹配是n的话
我们可以去找属于自己的列，如图
说明满足第一行的匹配在第二列，但是我现在匹配的是第三列，这个时候就要把这两列交换一下，得到以下结果
这个时候第二行匹配错了，所以2,3行交换，然后得到的结果就匹配完成了
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
struct sss
{
int x,y;
}a[];
int n;
int mp[][];
int vis[];
int girl[];
int dfs(int x)
{
for(int i=;i<=n;i++)
{
if(mp[x][i]&&vis[i]==)
{
vis[i]=;
if(girl[i]==||dfs(girl[i]))
{
girl[i]=x;
return ;
}
}
}
return ;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(girl,,sizeof(girl));
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
scanf("%d",&mp[i][j]);
}
int sum=;
for(int i=;i<=n;i++)
{
memset(vis,,sizeof(vis));
sum+=dfs(i);
}
if(sum!=n) printf("-1\n");//看是否满足全部匹配到了
else{
int num=;
for(int i=;i<=n;i++)
{
if(i!=girl[i])//灵活利用girl数组记录了匹配的行
{
for(int j=i+;j<=n;j++)//如果当前行匹配出错，找出需要匹配的行在哪里
{
if(i==girl[j])
{
int t;
t=girl[i];
girl[i]=girl[j];
girl[j]=t;
a[num].x=i;
a[num].y=j;
num++;
break;
}
}
}
}
printf("%d\n",num);
for(int i=;i<num;i++)
{
printf("C %d %d\n",a[i].x,a[i].y);
}
}
}
}