设输入矩阵为A，输出矩阵为B，目标矩阵为C（零矩阵）。
方便起见，矩阵行列下标均从1开始。
考虑A矩阵元素a（i，j），B矩阵中与其相邻的元素 b（i，j），b（i - 1， j），b（i + 1，j），b（i，j - 1），b（i，j + 1） （#）。
有c（i，j）= 0 = a（i，j） ^ （∑ b（i，j） % 2）。
进一步有a（i，j） ^ 0 = a（i，j） = a（i，j） ^ a（i，j） ^ （∑ b（i，j） % 2） = ∑ b（i，j） % 2 (*)。
进一步考虑异或与模2加之间的关系：∑ b（i，j） % 2 = ^ B(i, j)，其中B（i，j）表示（#）式5个元素的集合。
带入（*）：^ B(i, j) = a（i，j）。这是我们需要的方程组。
（注：考虑边界上的元素，只需将不在矩阵范围内的b元素全部置零即可。）
将b（i，j）映射到x（（i - 1） * 5 + j）（x下标从1到5 * 6)。
下面考虑解异或方程组AX= B。（与前面的表达无关）
a11 * x1 ^ a12 * x2 ^...^ a1n * xn = b1 ①
...
an1 * x1 ^ an2 * x2 ^...^ann * xn = bn ②
A,X,B均为0-1矩阵。
考虑消元，现在看系数矩阵A的第一列，若全部元素均为0，直接转到下一列，并且有方程组有多解。
若存在ai1 = 1,将其与第一行交换（这样做的目的是为了得到上三角阵）。
此时只需考虑剩余所有 1 < j ≤ n, 且aj1 = 1。有：
a11 * x1 ^ a12 * x2 ^...^ a1n * xn = b1 ①
aj1 * x1 ^ aj2 * x2 ^...^ ajn * xn = bj ②
① ^ ②：
（a11 * x1 ^ a12 * x2 ^...^ a1n * xn） ^ （aj1 * x1 ^ aj2 * x2 ^...^ ajn * xn） = b1 ^ bj。
即：（a11 * x1 ^ aj1 * x1） ^ （a12 * x2 ^ aj2 * x2） ^...^ （a1n * xn ^ ajn * xn) = b1 ^ bj 。
易于验证：a * x ^ b ^ x = (a ^ b) * x，因此进一步有：
（a11 ^ aj1）*x1 ^ （a12 ^ aj2）*x2 ^ .... ^ （a1n ^ ajn）*xn = b1 ^ bj 。
因而第j行x1的系数更新为1 ^ 1 即0 。
对增广阵如此消元至得到上三角阵即可得到答案。
http://poj.org/problem?id=1222
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxx = ;
const int maxy = ;
const int maxm = maxx * maxy;
const int maxn = maxm + ;
int A[maxn][maxn], B[maxn];
int C[maxn][maxn];
int dx[] = {, , , -, };
int dy[] = {, -, , , };
int pos(int i, int j) { return (i - ) * maxy + j; }
bool in_range(int i, int j) { return i >= && i <= maxx && j >= && j <= maxy; }
void solve(){
memset(C, , sizeof C);
for(int i = , k = ; i <= maxx; i++) for(int j = ; j <= maxy; j++, k++){
//the k-th column of the coefficient matrix
for(int u = ; u < ; u++){
int nx = i + dx[u], ny = j + dy[u], p = pos(nx, ny);
if(in_range(nx, ny)) C[k][p] = ;
}
C[k][maxm + ] = A[i][j];
}
for(int i = ; i <= maxm; i++){
//eliminate for X(i)
for(int j = i; j <= maxm; j++){
//highlighting A[j][]
if(C[j][i]){
swap(C[i], C[j]);
break;
}
}
for(int j = i + ; j <= maxm; j++){
if(!C[j][i]) continue;
for(int k = i; k <= maxm + ; k++) C[j][k] ^= C[i][k];
}
}
//retrieve the ans
for(int i = maxm; i >= ; i--){
B[i] = C[i][maxm + ];
for(int j = i + ; j <= maxm; j++) if(C[i][j]) B[i] ^= B[j];
}
for(int i = ; i <= maxx; i++){
printf("%d", B[pos(i, )]);
for(int j = ; j <= maxy; j++){
int p = pos(i, j);
printf(" %d", B[p]);
}
printf("\n");
}
} int main(){
freopen("in.txt", "r", stdin);
int T, kase = ;
scanf("%d", &T);
while(T--){
printf("PUZZLE #%d\n", ++kase);
for(int i = ; i <= maxx; i++) for(int j = ; j <= maxy; j++) scanf("%d", &A[i][j]);
solve();
}
return ;
}