poj-1222
给出一个5*6的01矩阵，每按一个格点就会将该格点及其4个方向上的格点（如果有的话）数值翻转，试给出一个方案使得最终所有格点均为0.
高斯消元经典例题，拿来测试一下自己的模版是否正确。
这题比较精妙的地方在于建方程：变元有30个，分别代表5*6矩阵中是否按下每一个按钮。而所有操作完成后每个格点的状态显然可以用这30个变元进行线性表示。不过这里的加法应该映射为异或+，稍微修改一下板子并且注意多组数据即可。
1/*
2使用指南：
3 读入"整形"增广矩阵a，修改行列信息equ、var。
4 从零开始编号，则行为[0, equ - 1], 列为[0, var];
5 返回值：
6 返回0说明有整数解，结果存放在x数组中
7 返回-2说明有浮点解，需要修改数据类型再运算
8 返回-1时无解
9 返回正数k时说明有k个自由变元，自由变元存放在flag中；
10Tips:
11 处理过程可能爆int
12*/
13
14const int maxn = 1e2;
15//有equ个等式，var个变量，那么增广矩阵有equ行，var + 1列；模版中从0开始标号。
16int equ, var;
17int a[maxn][maxn];
18//x是解集，flag标记是否自由
19int x[maxn], flag[maxn];
20
21int gauss(){
22 int i, j;
23 for(i = 0, j = 0; i < equ && j < var; i++, j++){
24 int l = i;
25 for(int k = i + 1; k < equ; k++) if(abs(a[k][j] > a[l][j])) l = k;
26 if(l != i) swap(a[l], a[i]);
27 //i行及以下的该列全为0，转而处理下一列。
28 if(a[i][j] == 0){
29 i--; continue;
30 }
31 for(int k = i + 1; k < equ; k++) if(a[k][j]){
32 for(int col = j; col <= var; col++) a[k][col] = a[k][col] ^ a[i][col];
33 }
34 }
35 //循环完成后，i是有效行数，也就是秩（？）；
36
37
38 //(I)存在(0, 0, ... ,0, k!=0)的结构存在，即无解,返回-1
39 for(int k = i; k < equ; k++) if(a[k][var] != 0) return -1;
40
41 //(II)存在自由变元，返回变元数量，并且在flag数组中标记出所有的自由变元。
42 if(j < var){
43 //i是秩，[0, i - 1]均为非全零的行
44 for(int k = i - 1; k >= 0; k--){
45 int cnt = 0, free_id = -1;
46 for(int col = 0; col < var; col++) if(a[k][col] && flag[col]){
47 cnt++;
48 free_id = col;
49 }
50 //一定存在至少一个自由变元，不然一定会被向下过程消去。
51 assert(free_id != -1);
52
53 //有两个及以上变元，那么无法确定这些变元
54 if(cnt >= 2) continue;
55
56 // 注释原因:求解变元会涉及到小数？故注释掉，实际操作时根据具体情况处理
57 // //只剩一个变元free_id，可以求解出来。
58 // int temp = a[k][var];
59 // for(int col = 0; col < var; col++) if(a[k][col] && col != free_id) temp -= a[k][col] * x[col];
60 // x[free_id] = tmep / a[k][free_id];
61
62 flag[free_id] = 0;
63 }
64 return var - i;
65 }
66
67 //(III)求解方程，此时保证有唯一解:如果全部为正整数解，返回0，如果出现浮点数解，返回-2；
68 for(int i = var - 1; i >= 0; i--){
69 int tmep = a[i][var];
70 for(int j = i + 1; j < var; j++) if(a[i][j]) tmep ^= a[i][j] * x[j];
71 x[i] = temp;
72 }
73 return 0;
74}
75
76
77int dx[] = {1, -1, 0, 0};
78int dy[] = {0, 0, 1, -1};
79bool valid(int x, int y){
80 return x >= 0 && y >= 0 && x < 5 && y < 6;
81}
82
83void fun(){
84 for(int i = 0; i < 30; i++) {
85 a[i][i] = 1;
86 int x = i / 6, y = i % 6;
87 for(int j = 0; j < 4; j++){
88 int nx = x + dx[j], ny = y + dy[j];
89 if(valid(nx, ny)){
90 a[nx * 6 + ny][i] = 1;
91 }
92 }
93 }
94}
95
96int main() {
97 // Fastin;
98 equ = var = 30;
99 TTT{
100 printf("PUZZLE #%d\n", _);
101 int top = 0;
102 clr(a, 0); fun();
103 for(int i = 0; i < 30; i++) scnaf("%d", a[top++] + 30);
104 assert(gauss() == 0);
105
106 top = 0;
107 for(int i = 0; i < 5; i++){
108 for(int j = 0; j < 6; j++) printf("%d ", x[top++]);
109 printf("\n");
110 }
111
112 }
113 return 0;
114}