题目链接:http://hihocoder.com/problemset/problem/1196
#include <bits/stdc++.h>
using namespace std; typedef pair<int, int> pii;
const int maxn = ;
int equ, var;
int a[maxn][maxn];
int x[maxn];
int free_x[maxn];
int free_num;
int ret; int gauss() {
int max_r, col, k;
free_num = ;
for(k = , col = ; k < equ && col < var; k++, col++) {
max_r = k;
for(int i = k + ; i < equ; i++) {
if(abs(a[i][col]) > abs(a[max_r][col]))
max_r = i;
}
if(a[max_r][col] == ) {
k--;
free_x[free_num++] = col;
continue;
}
if(max_r != k) {
for(int j = col; j < var + ; j++)
swap(a[k][j], a[max_r][j]);
}
for(int i = k + ; i < equ; i++) {
if(a[i][col] != ) {
for(int j = col; j < var + ; j++) {
a[i][j] ^= a[k][j];
}
}
}
}
for(int i = k; i < equ; i++) {
if(a[i][col] != )
return -;
}
if(k < var) return var - k;
for(int i = var - ; i >= ; i--) {
x[i] = a[i][var];
for(int j = i + ; j < var; j++) {
x[i] ^= (a[i][j] & x[j]);
}
}
return ;
} char G[maxn][maxn];
int n, m; int main() {
// freopen("in", "r", stdin);
m = , n = ;
var = equ = ;
ret = ;
memset(a, , sizeof(a));
for(int i = ; i < n; i++) scanf("%s", G[i]);
for(int i = ; i < m; i++) {
for(int j = ; j < n; j++) {
if(G[i][j] == '') a[i*n+j][var] = ;
else a[i*n+j][var] = ;
}
}
for(int i = ; i < ; i++) {
a[i][i] = ;
if(i % != ) a[i-][i] = ;
if(i % != ) a[i+][i] = ;
if(i > ) a[i-][i] = ;
if(i < ) a[i+][i] = ;
}
int v = gauss();
if(v == -) ret = -;
else if(v != ) {
ret = maxn;
int tot = << v;
for(int i = ; i < tot; i++) {
int cnt = ;
for(int j = ; j < v; j++) {
if(i&(<<j)) {
x[free_x[j]] = ;
cnt++;
}
else x[free_x[j]] = ;
}
for(int j = var - v - ; j >= ; j--) {
int idx;
for(idx = j; idx < var; idx++) {
if(a[j][idx]) break;
}
x[idx] = a[j][var];
for(int l = idx + ; l < var; l++) {
if(a[j][l]) x[idx] ^= x[l];
}
cnt += x[idx];
}
ret = min(ret, cnt);
}
}
else for(int i = ; i < var; i++) ret += x[i];
printf("%d\n", ret);
vector<pii> va;
for(int i = ; i < ; i++) {
if(x[i]) {
int pos = i + ;
int r = , c = ;
while(pos > ) {
pos -= ;
r++;
}
c += pos;
va.push_back(pii(r, c));
}
}
sort(va.begin(), va.end());
for(int i = ; i < va.size(); i++) {
printf("%d %d\n", va[i].first, va[i].second);
}
return ;
}