题目链接：http://poj.org/problem?id=1222
题意：开关是四连通的，每按一个就会翻转自己以及附近的四个格（假如有）。问需要翻转几个，使他们都变成关。
把每一个灯看作一个未知量，可以有30个未知量，给每一个未知量从0~29编号，再列30个方程，每一个方程中描述每一个灯被翻转后其相邻等的状态变化，倒着考虑，把全关状态翻成当前状态就行了。
转移矩阵是这样的，很好理解。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 33; 5 int equ, var; 6 int a[maxn][maxn]; 7 int x[maxn]; 8 int free_x[maxn]; 9 int free_num; 10 11 int gauss() { 12 int max_r, col, k; 13 free_num = 0; 14 for(k = 0, col = 0; k < equ && col < var; k++, col++) { 15 max_r = k; 16 for(int i = k + 1; i < equ; i++) { 17 if(abs(a[i][col]) > abs(a[max_r][col])) 18 max_r = i; 19 } 20 if(a[max_r][col] == 0) { 21 k--; 22 free_x[free_num++] = col; 23 continue; 24 } 25 if(max_r != k) { 26 for(int j = col; j < var + 1; j++) 27 swap(a[k][j], a[max_r][j]); 28 } 29 for(int i = k + 1; i < equ; i++) { 30 if(a[i][col] != 0) { 31 for(int j = col; j < var + 1; j++) { 32 a[i][j] ^= a[k][j]; 33 } 34 } 35 } 36 } 37 for(int i = k; i < equ; i++) { 38 if(a[i][col] != 0) 39 return -1; 40 } 41 if(k < var) 42 return var - k; 43 for(int i = var - 1; i >= 0; i--) { 44 x[i] = a[i][var]; 45 for(int j = i + 1; j < var; j++) { 46 x[i] ^= (a[i][j] & x[j]); 47 } 48 } 49 return 0; 50 } 51 52 int main() { 53 // freopen("in", "r", stdin); 54 equ = 30, var = 30; 55 int T, _ = 1; 56 scanf("%d", &T); 57 while(T--) { 58 memset(a, 0, sizeof(a)); 59 memset(x, 0, sizeof(x)); 60 memset(free_x, 0, sizeof(free_x)); 61 for(int i = 0; i < 30; i++) { 62 scanf("%d", &a[i][var]); 63 } 64 for(int i = 0; i < 30; i++) { 65 a[i][i] = 1; 66 if(i % 6 != 0) a[i-1][i] = 1; 67 if(i % 6 != 5) a[i+1][i] = 1; 68 if(i > 5) a[i-6][i] = 1; 69 if(i < 24) a[i+6][i] = 1; 70 } 71 int v = gauss(); 72 int cnt = 0; 73 printf("PUZZLE #%d ", _++); 74 for(int i = 0; i < 5; i++) { 75 for(int j = 0; j < 6; j++) { 76 printf("%d ", x[cnt++]); 77 } 78 printf(" "); 79 } 80 } 81 return 0; 82 }