2014
02-17

Swap

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?

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.

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.

2
0 1
1 0
2
1 0
1 0

1
R 1 2
-1

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110;
int n, g[N][N], cx[N], cy[N], ans1[N*2], ans2[N*2];
bool used[N];

bool dfs( int u )
{
for ( int i = 1; i <= n; ++i ) if ( g[u][i] && !used[i] ) {
used[i] = true;
if ( cy[i] == -1 || dfs( cy[i] ) ) {
cy[i] = u;
cx[u] = i;
return true;
}
}
return false;
}
int match()
{
int res = 0;
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
for ( int i = 1; i <= n; ++i ){
memset( used, 0, sizeof(used));
if ( dfs(i) ) res++;
else break;
}
return res;
}
int main()
{
while ( scanf("%d", &n) != EOF ) {
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= n; ++j ) scanf("%d", &g[i][j]);
if ( match() != n ) {
printf("-1\n");
continue;
}
int len = 0;
for ( int i = 1; i <= n; ++i ) {
int mark = i, tmp;
for ( int j = i; j <= n; ++j )
if ( cy[mark] > cy[j] ) mark = j;
if ( mark == i ) continue;
ans1[++len] = i, ans2[len] = mark;
tmp = cy[mark];
cy[mark] = cy[i];
cy[i] = tmp;
}
printf("%d\n", len);
for ( int i = 1; i <= len; ++i ) printf("C %d %d\n", ans1[i], ans2[i]);
}
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮