题目链接：http://poj.org/problem?id=1753
题意：同上。
这回翻来翻去要考虑自由变元了，假设返回了自由变元数量，则需要枚举自由变元。
/*
━━━━━┒ギリギリ♂ eye！
┓┏┓┏┓┃キリキリ♂ mind！
┛┗┛┗┛┃＼○／
┓┏┓┏┓┃ /
┛┗┛┗┛┃ノ)
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┃┃┃┃┃┃
┻┻┻┻┻┻
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std; const int maxn = ;
int equ, var;
int a[maxn][maxn];
int x[maxn];
int free_x[maxn];
int free_num;
int ret1, ret2; 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; int main() {
// freopen("in", "r", stdin);
n = ;
var = equ = ;
ret1 = ret2 = ;
memset(a, , sizeof(a));
for(int i = ; i < n; i++) scanf("%s", G[i]);
for(int i = ; i < n; i++) {
for(int j = ; j < n; j++) {
if(G[i][j] == 'b') a[i*n+j][var] = ;
else a[i*n+j][var] = ;
}
}
for(int i = ; i < n; i++) {
for(int j = ; j < n; j++) {
int q = i * n + j;
a[q][q] = ;
if(i > ) a[(i-)*n+j][q] = ;
if(i < n - ) a[(i+)*n+j][q] = ;
if(j > ) a[i*n+j-][q] = ;
if(j < n - ) a[i*n+j+][q] = ;
}
}
int v1 = gauss();
if(v1 == -) ret1 = -;
else if(v1 != ) {
ret1 = maxn;
int tot = << v1;
for(int i = ; i < tot; i++) {
int cnt = ;
for(int j = ; j < v1; j++) {
if(i&(<<j)) {
x[free_x[j]] = ;
cnt++;
}
else x[free_x[j]] = ;
}
for(int j = var - v1 - ; 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];
}
ret1 = min(ret1, cnt);
}
}
else for(int i = ; i < var; i++) ret1 += x[i]; memset(a, , sizeof(a));
for(int i = ; i < n; i++) {
for(int j = ; j < n; j++) {
if(G[i][j] == 'w') a[i*n+j][var] = ;
else a[i*n+j][var] = ;
}
}
for(int i = ; i < n; i++) {
for(int j = ; j < n; j++) {
int q = i * n + j;
a[q][q] = ;
if(i > ) a[(i-)*n+j][q] = ;
if(i < n - ) a[(i+)*n+j][q] = ;
if(j > ) a[i*n+j-][q] = ;
if(j < n - ) a[i*n+j+][q] = ;
}
} int v2 = gauss();
if(v2 == -) ret2 = -;
else if(v2 != ) {
ret2 = maxn;
int tot = << v2;
for(int i = ; i < tot; i++) {
int cnt = ;
for(int j = ; j < v2; j++) {
if(i&(<<j)) {
x[free_x[j]] = ;
cnt++;
}
else x[free_x[j]] = ;
}
for(int j = var - v2 - ; 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];
}
ret2 = min(ret2, cnt);
}
}
else for(int i = ; i < var; i++) ret2 += x[i];
if(ret1==-&&ret2==-) puts("Impossible");
else if(v1==-) printf("%d\n", ret2);
else if(ret2==-) printf("%d\n", ret1);
else printf("%d\n", min(ret1, ret2));
return ;
}