http://poj.org/problem?id=1681
题意“：
一个n*n 的木板 ，每个格子 都 可以 染成 白色和黄色，（ 一旦我们对也个格子染色 ，他的上下左右 都将改变颜色）；
给定一个初始状态 ， 求将 所有的 格子 染成黄色 最少需要染几次？ 若 不能 染成 输出 inf。
题解:
和1222开关 问题一样，只不过是 将 开关 换成了 染色。
E(a) = xa*A11 ^ xb*A12 ^ xc*A13 ^ S(a);
E(b) = xa*A21 ^ xb*A22 ^ xc*A23 ^ S(b);
E(c) = xa*A31 ^ xb*A32 ^ xc*A33 ^ S(c);
将是s 移项 将左边 变为系数矩阵，求解 。
我认为 ：因为 要求最小，我们只要 统计 确定的解 的个数就可，（ 不确定的将不影响结果） （若有不对 请 大牛指点）
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 300
15 #define eps 1e-12
16 #define inf 100000000
17 #define mx 1<<60
18 #define ll __int64
19 const double pi = acos(-1.0);
20 using namespace std;
21 int n;
22 int find(int i,int j)
23 {
24 return i*n + j ;
25 }
26 int a[maxn][maxn] ;
27 int free_x[maxn] ;
28 int x[maxn];
29 void init()
30 {
31 CL(a,0);
32 int i,j,y;
33
34 for(i = 0 ;i < n;i++)
35 {
36 for(j = 0;j< n;j++)
37 {
38 int x = find(i,j);
39 a[x][x] = 1;
40 if(i - 1>=0)
41 {
42 y = find(i - 1,j);
43 a[x][y] = 1;
44 }
45 if(j + 1< n)
46 {
47 y = find(i,j +1);
48 a[x][y] = 1;
49 }
50 if(i + 1 < n)
51 {
52 y = find(i + 1,j);
53 a[x][y] = 1;
54
55 }
56 if(j - 1 >=0)
57 {
58 y = find(i,j - 1);
59 a[x][y] = 1;
60 }
61 }
62 }
63 }
64 int gcd(int x,int y)
65 {
66 int t ;
67 while(y)
68 {
69 t = y;
70 y = x%y;
71 x = t;
72 }
73 return x;
74 }
75 int lcm( int x,int y)
76 {
77 return (x*y)/gcd(x,y);
78 }
79 int Gauss(int var,int equ)
80 {
81 int i,j,free_index;
82 int max_r,k,col;
83 int LCM,tmp;
84 int free_num;
85 for(i =0 ; i<=var;i++)
86 {
87 free_x[i] = 1;
88 x[i] = 0 ;
89 }
90 for(k = 0 ,col = 0;k<equ&&col<var;k++,col++)
91 {
92 max_r= k;
93 for(i = k+1;i<equ;i++)
94 {
95 if(abs(a[i][col]) > abs(a[max_r][col]))max_r = i;
96 }
97 if(a[max_r][col] == 0)
98 {
99 k--;
100 continue ;
101 }
102 if(max_r!=k)
103 {
104 for(i = 0;i < var+1;i++)
105 {
106 swap(a[k][i],a[max_r][i]);
107 }
108 }
109 for(i = k + 1;i<equ;i++)
110 {
111 if(a[i][col] !=0)
112 {
113 //LCM = lcm(abs(a[k][col]),abs(a[i][col]));
114 //int ta = LCM/a[i][col],tb = LCM/a[k][col] ;
115 //if(a[i][col]*a[k][col] < 0) tb = - tb;
116 for(j = col;j<var + 1;j++)
117 {
118 a[i][j] = a[i][j]^a[k][j];
119 }
120 }
121 }
122 }
123 for(i = k;i < equ;i++)
124 {
125 if(a[i][col] != 0) return -1;
126 }
127 int ans = 0 ;
128 for(i = var - 1;i >= 0;i--)
129 {
130 int tmp = a[i][var];
131 for(j = i + 1;j<var;j++)
132 {
133 if(a[i][j]!= 0) tmp^=a[i][j]*x[j];
134 }
135 ans+=tmp;
136 x[i] = tmp ;
137 }
138 return ans ;
139
140 /*if(k < var)
141 {
142
143 for(i = k - 1;i>=0;i--)
144 {
145 free_num = 0;
146 for(j = 0 ; j< var;j++)
147 {
148 if(a[i][j] != 0&&free_x[j])
149 {
150 free_num ++;
151 free_index = j;
152 }
153 }
154 if(free_num >1) continue ;
155 tmp = a[i][var];
156 for(j = 0; j<var;j++)
157 {
158 if(a[i][j]!=0 && j != free_index)tmp -=a[i][j] * x[j];
159 }
160 x[free_index] = tmp/ a[i][free_index];
161 free_x[free_index] = 0 ;
162 }
163 return var - k;
164 }
165 for(i = var - 1;i>=0;i--)
166 {
167 tmp = a[i][var];
168 for(j = i + 1;j<var;j++)
169 {
170 if(a[i][j] != 0) tmp -= a[i][j]*x[j] ;
171 }
172 if(tmp % a[i][i]) return -2;
173 x[i] = tmp/a[i][i] ;
174 }
175 return 0 ;*/
176
177 }
178 char str[20][20];
179 int main()
180 {
181 int t,i,j;
182 scanf("%d",&t);
183 while(t--)
184 {
185 scanf("%d",&n);
186 for(i = 0 ; i< n;i++)
187 {
188 scanf("%s",str[i]);
189 }
190 init();
191 int f = 0;
192 for(i = 0 ; i<n;i++)
193 {
194 for(j = 0 ;j< n;j++)
195 {
196 if(str[i][j] =='w')
197 {
198 f = 1 ;
199 a[i*n + j][n*n] = 1;
200 }
201 }
202 }
203 if(f == 0)
204 {
205 printf("0\n");
206 continue ;
207 }
208 int ans = Gauss(n*n,n*n);
209 if(ans == -1)
210 {
211 printf("inf\n");
212 }
213 else
214 {
215 printf("%d\n",ans);
216 }
217
218 }
219 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 300
15 #define eps 1e-12
16 #define inf 100000000
17 #define mx 1<<60
18 #define ll __int64
19 const double pi = acos(-1.0);
20 using namespace std;
21 int n;
22 int find(int i,int j)
23 {
24 return i*n + j ;
25 }
26 int a[maxn][maxn] ;
27 int free_x[maxn] ;
28 int x[maxn];
29 void init()
30 {
31 CL(a,0);
32 int i,j,y;
33
34 for(i = 0 ;i < n;i++)
35 {
36 for(j = 0;j< n;j++)
37 {
38 int x = find(i,j);
39 a[x][x] = 1;
40 if(i - 1>=0)
41 {
42 y = find(i - 1,j);
43 a[x][y] = 1;
44 }
45 if(j + 1< n)
46 {
47 y = find(i,j +1);
48 a[x][y] = 1;
49 }
50 if(i + 1 < n)
51 {
52 y = find(i + 1,j);
53 a[x][y] = 1;
54
55 }
56 if(j - 1 >=0)
57 {
58 y = find(i,j - 1);
59 a[x][y] = 1;
60 }
61 }
62 }
63 }
64 int gcd(int x,int y)
65 {
66 int t ;
67 while(y)
68 {
69 t = y;
70 y = x%y;
71 x = t;
72 }
73 return x;
74 }
75 int lcm( int x,int y)
76 {
77 return (x*y)/gcd(x,y);
78 }
79 int Gauss(int var,int equ)
80 {
81 int i,j,free_index;
82 int max_r,k,col;
83 int LCM,tmp;
84 int free_num;
85 for(i =0 ; i<=var;i++)
86 {
87 free_x[i] = 1;
88 x[i] = 0 ;
89 }
90 for(k = 0 ,col = 0;k<equ&&col<var;k++,col++)
91 {
92 max_r= k;
93 for(i = k+1;i<equ;i++)
94 {
95 if(abs(a[i][col]) > abs(a[max_r][col]))max_r = i;
96 }
97 if(a[max_r][col] == 0)
98 {
99 k--;
100 continue ;
101 }
102 if(max_r!=k)
103 {
104 for(i = 0;i < var+1;i++)
105 {
106 swap(a[k][i],a[max_r][i]);
107 }
108 }
109 for(i = k + 1;i<equ;i++)
110 {
111 if(a[i][col] !=0)
112 {
113 //LCM = lcm(abs(a[k][col]),abs(a[i][col]));
114 //int ta = LCM/a[i][col],tb = LCM/a[k][col] ;
115 //if(a[i][col]*a[k][col] < 0) tb = - tb;
116 for(j = col;j<var + 1;j++)
117 {
118 a[i][j] = a[i][j]^a[k][j];
119 }
120 }
121 }
122 }
123 for(i = k;i < equ;i++)
124 {
125 if(a[i][col] != 0) return -1;
126 }
127 int ans = 0 ;
128 for(i = var - 1;i >= 0;i--)
129 {
130 int tmp = a[i][var];
131 for(j = i + 1;j<var;j++)
132 {
133 if(a[i][j]!= 0) tmp^=a[i][j]*x[j];
134 }
135 ans+=tmp;
136 x[i] = tmp ;
137 }
138 return ans ;
139
140 /*if(k < var)
141 {
142
143 for(i = k - 1;i>=0;i--)
144 {
145 free_num = 0;
146 for(j = 0 ; j< var;j++)
147 {
148 if(a[i][j] != 0&&free_x[j])
149 {
150 free_num ++;
151 free_index = j;
152 }
153 }
154 if(free_num >1) continue ;
155 tmp = a[i][var];
156 for(j = 0; j<var;j++)
157 {
158 if(a[i][j]!=0 && j != free_index)tmp -=a[i][j] * x[j];
159 }
160 x[free_index] = tmp/ a[i][free_index];
161 free_x[free_index] = 0 ;
162 }
163 return var - k;
164 }
165 for(i = var - 1;i>=0;i--)
166 {
167 tmp = a[i][var];
168 for(j = i + 1;j<var;j++)
169 {
170 if(a[i][j] != 0) tmp -= a[i][j]*x[j] ;
171 }
172 if(tmp % a[i][i]) return -2;
173 x[i] = tmp/a[i][i] ;
174 }
175 return 0 ;*/
176
177 }
178 char str[20][20];
179 int main()
180 {
181 int t,i,j;
182 scanf("%d",&t);
183 while(t--)
184 {
185 scanf("%d",&n);
186 for(i = 0 ; i< n;i++)
187 {
188 scanf("%s",str[i]);
189 }
190 init();
191 int f = 0;
192 for(i = 0 ; i<n;i++)
193 {
194 for(j = 0 ;j< n;j++)
195 {
196 if(str[i][j] =='w')
197 {
198 f = 1 ;
199 a[i*n + j][n*n] = 1;
200 }
201 }
202 }
203 if(f == 0)
204 {
205 printf("0\n");
206 continue ;
207 }
208 int ans = Gauss(n*n,n*n);
209 if(ans == -1)
210 {
211 printf("inf\n");
212 }
213 else
214 {
215 printf("%d\n",ans);
216 }
217
218 }
219 }