TJU/HDU Matrix Swapping//MAXMATCH

3295.  
Matrix Swapping
Time Limit: 1.0 Seconds   
Memory Limit: 65536K   
Special Judge
Total Runs: 408   
Accepted Runs: 108
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? Source: Multi-School Training Contest - TOJ Site #1

Input

There 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), separated by space, indicating the N * N matrix.

Output

For 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 not 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

Author:HE, Liang
 
Note: Special judge problem, you may get "Wrong Answer"when output in wrong format.
 
 
 
이 문제는 아주 잘 냈어, 확실히.
처음에 나는 도대체 매칭으로 그를 할 수 있을지 계속 생각했다.두 줄을 교환하면 잘못된 전환을 초래할 수 있는지 생각하고 있기 때문이다.
나중에 생각해 보니 이 제목은 사실 우리가 N개의 동행하지 않는 다른 열의 1을 찾으러 가기 위해서이다. 그래서 우리는 줄이나 열을 교환할 때 이미 대각선에 있는 원소에 영향을 주지 않을 것이다. (이 점은 내가 의심스럽다. 나는 그가 대각선에 있는 원소의 판단 문장을 바꾸지 않을 것을 보증했다. 그러나 모두 WA였다. 왜 그런지 모르겠다)
또 교환된 문장을 출력할 때 줄 교환이나 열 교환에 집중하고 이 둘 중 하나를 선택하면 된다.
 
#include#includeint n;int map[101][101],link[101];bool mat[101][101],used[101];int change[101][2];bool can(int t){    for(int i=1;i<=n;i++)    if(used[i]==false&&mat[t][i])    {        used[i]=true;        if(link[i]==-1||can(link[i]))        {            link[i]=t;            return true;        }    }    return false;}int MaxMatch(){    memset(link,-1,sizeof(link));    for(int i=1;i<=n;i++)    {        memset(used,false,sizeof(used));        if(!can(i)) return false;    }    return true;}int main(){    while(scanf("%d",&n)!=EOF)    {        int cas=0;        for(int i=1;i<=n;i++)          for(int j=1;j<=n;j++)          {              scanf("%d",&map[i][j]);              if(map[i][j]==1) mat[i][j]=true,cas++;              else mat[i][j]=false;          }
         //if(cas==n*n) printf("0/n");       //else        if(cas