此题可有对角线都是1的方阵进行 行变换或列变换 得到。
如果这样想就可以知道， 每行只选一个列，要把所有的列全部选完， 而且最后只需进行行变换就可以转变成对角线全为一
Swap
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 892 Accepted Submission(s): 283Special Judge
Problem Description
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?
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), separating 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 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
Source
Recommend
gaojie
#include#include #include using namespace std;#define N 110int g[N][N];int n;int mark[N],pre[N];int dfs(int s){ for(int i=1;i<=n;i++) { if(g[s][i]==0||mark[i]==1) continue; mark[i]=1; if(pre[i]==-1||dfs(pre[i])) { pre[i]=s; return 1; } } return 0;}int main(){ while(scanf("%d",&n)!=EOF) { memset(g,0,sizeof(g)); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { int tmp; scanf("%d",&tmp); if(tmp==1) g[j][i]=1; } } int sum=0; memset(pre,-1,sizeof(pre)); for(int i=1;i<=n;i++) { memset(mark,0,sizeof(mark)); sum+=dfs(i); } if(sum!=n) printf("-1\n"); else { int ans[110]; int cnt=1; for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { if(pre[j]==i) { ans[cnt++]=j; swap(pre[j],pre[i]); break; } } } printf("%d\n",n); for(int i=1;i<=n;i++) printf("R %d %d\n",i,ans[i]); } } return 0;}