题目链接：http://poj.org/problem?id=1681
题意：还是翻格子的题，但是这里有可能出现自由变元，这时候枚举一下就行。。（其实这题直接状压枚举就行）
1 /* 2 ━━━━━┒ギリギリ♂ eye！ 3 ┓┏┓┏┓┃キリキリ♂ mind！ 4 ┛┗┛┗┛┃＼○／ 5 ┓┏┓┏┓┃ / 6 ┛┗┛┗┛┃ノ) 7 ┓┏┓┏┓┃ 8 ┛┗┛┗┛┃ 9 ┓┏┓┏┓┃ 10 ┛┗┛┗┛┃ 11 ┓┏┓┏┓┃ 12 ┛┗┛┗┛┃ 13 ┓┏┓┏┓┃ 14 ┃┃┃┃┃┃ 15 ┻┻┻┻┻┻ 16 */ 17 #include <algorithm> 18 #include <iostream> 19 #include <iomanip> 20 #include <cstring> 21 #include <climits> 22 #include <complex> 23 #include <cassert> 24 #include <cstdio> 25 #include <bitset> 26 #include <vector> 27 #include <deque> 28 #include <queue> 29 #include <stack> 30 #include <ctime> 31 #include <set> 32 #include <map> 33 #include <cmath> 34 using namespace std; 35 36 const int maxn = 333; 37 int equ, var; 38 int a[maxn][maxn]; 39 int x[maxn]; 40 int free_x[maxn]; 41 int free_num; 42 43 int gauss() { 44 int max_r, col, k; 45 free_num = 0; 46 for(k = 0, col = 0; k < equ && col < var; k++, col++) { 47 max_r = k; 48 for(int i = k + 1; i < equ; i++) { 49 if(abs(a[i][col]) > abs(a[max_r][col])) 50 max_r = i; 51 } 52 if(a[max_r][col] == 0) { 53 k--; 54 free_x[free_num++] = col; 55 continue; 56 } 57 if(max_r != k) { 58 for(int j = col; j < var + 1; j++) 59 swap(a[k][j], a[max_r][j]); 60 } 61 for(int i = k + 1; i < equ; i++) { 62 if(a[i][col] != 0) { 63 for(int j = col; j < var + 1; j++) { 64 a[i][j] ^= a[k][j]; 65 } 66 } 67 } 68 } 69 for(int i = k; i < equ; i++) { 70 if(a[i][col] != 0) 71 return -1; 72 } 73 if(k < var) return var - k; 74 for(int i = var - 1; i >= 0; i--) { 75 x[i] = a[i][var]; 76 for(int j = i + 1; j < var; j++) { 77 x[i] ^= (a[i][j] & x[j]); 78 } 79 } 80 return 0; 81 } 82 83 const int dx[6] = {0, 0, 0, 1, -1}; 84 const int dy[6] = {0, 1, -1, 0, 0}; 85 char G[22][22]; 86 int tmp[22][22]; 87 int n; 88 89 bool ok(int x, int y) { 90 return x >= 0 && x < n && y >= 0 && y < n; 91 } 92 93 int get(int x , int y) { 94 int c = G[x][y]; 95 for(int i = 0; i < 5; i++) { 96 int xx = x + dx[i]; 97 int yy = y + dy[i]; 98 if(ok(xx, yy)) c += tmp[xx][yy]; 99 } 100 return c % 2; 101 } 102 103 int calc() { 104 for(int i = 1; i < n; i++) { 105 for(int j = 0; j < n; j++) { 106 if(get(i-1, j)) tmp[i][j] = 1; 107 } 108 } 109 for(int i = 0; i < n; i++) { 110 if(get(n-1, i)) return -1; 111 } 112 int p = 0; 113 for(int i = 0; i < n; i++) { 114 for(int j = 0; j < n; j++) { 115 p += tmp[i][j]; 116 } 117 } 118 return p; 119 } 120 121 int solve(int t) { 122 n = t; 123 for(int i = 0; i < n; i++) { 124 for(int j = 0; j < n; j++) { 125 if(G[i][j] == 'w') G[i][j] = 1; 126 else G[i][j] = 0; 127 } 128 } 129 int ret = -1; 130 int nn = 1 << n; 131 for(int i = 0; i < nn; i++) { 132 memset(tmp, 0, sizeof(tmp)); 133 for(int j = 0; j < n; j++) tmp[0][n-j-1] = i >> j & 1; 134 int num = calc(); 135 if(num >= 0 && (ret < 0 || ret > num)) ret = num; 136 } 137 return ret; 138 } 139 140 int main() { 141 freopen("in", "r", stdin); 142 int T, _ = 1; 143 scanf("%d", &T); 144 while(T--) { 145 scanf("%d", &var); 146 memset(a, 0, sizeof(a)); 147 memset(x, 0, sizeof(x)); 148 memset(free_x, 0, sizeof(free_x)); 149 for(int i = 0; i < var; i++) { 150 scanf("%s", G[i]); 151 } 152 int cnt = 0; 153 for(int i = 0; i < var; i++) { 154 for(int j = 0; j < var; j++) { 155 if(G[i][j] == 'w') a[cnt][var*var] = 1; 156 cnt++; 157 } 158 } 159 int t = var; 160 var = var * var; 161 equ = var; 162 for(int i = 0; i < t; i++) { 163 for(int j = 0; j < t; j++) { 164 int q = i * t + j; 165 a[q][q] = 1; 166 if(i > 0) a[(i-1)*t+j][q] = 1; 167 if(i < t - 1) a[(i+1)*t+j][q] = 1; 168 if(j > 0) a[i*t+j-1][q] = 1; 169 if(j < t - 1) a[i*t+j+1][q] = 1; 170 } 171 } 172 // for(int i = 0; i < t; i++) { 173 // for(int j = 0; j < t; j++) { 174 // printf("%d ", a[i][j]); 175 // } 176 // printf(" "); 177 // } 178 int v = gauss(); 179 if(v == -1) puts("inf"); 180 else if(v == 0) { 181 int ret = 0; 182 for(int i = 0; i < var; i++) ret += x[i]; 183 printf("%d ", ret); 184 } 185 else { 186 int ret = solve(t); 187 if(ret < 0) puts("inf"); 188 else printf("%d ", ret); 189 } 190 } 191 return 0; 192 }
什么玩意，在发现有自由变元的时候，也求x的解不就好了，反正自由变元默认搞成0.
1 /* 2 ━━━━━┒ギリギリ♂ eye！ 3 ┓┏┓┏┓┃キリキリ♂ mind！ 4 ┛┗┛┗┛┃＼○／ 5 ┓┏┓┏┓┃ / 6 ┛┗┛┗┛┃ノ) 7 ┓┏┓┏┓┃ 8 ┛┗┛┗┛┃ 9 ┓┏┓┏┓┃ 10 ┛┗┛┗┛┃ 11 ┓┏┓┏┓┃ 12 ┛┗┛┗┛┃ 13 ┓┏┓┏┓┃ 14 ┃┃┃┃┃┃ 15 ┻┻┻┻┻┻ 16 */ 17 #include <algorithm> 18 #include <iostream> 19 #include <iomanip> 20 #include <cstring> 21 #include <climits> 22 #include <complex> 23 #include <cassert> 24 #include <cstdio> 25 #include <bitset> 26 #include <vector> 27 #include <deque> 28 #include <queue> 29 #include <stack> 30 #include <ctime> 31 #include <set> 32 #include <map> 33 #include <cmath> 34 using namespace std; 35 36 const int maxn = 333; 37 int equ, var; 38 int a[maxn][maxn]; 39 int x[maxn]; 40 int free_x[maxn]; 41 int free_num; 42 int ret; 43 44 int gauss() { 45 int max_r, col, k; 46 free_num = 0; 47 for(k = 0, col = 0; k < equ && col < var; k++, col++) { 48 max_r = k; 49 for(int i = k + 1; i < equ; i++) { 50 if(abs(a[i][col]) > abs(a[max_r][col])) 51 max_r = i; 52 } 53 if(a[max_r][col] == 0) { 54 k--; 55 free_x[free_num++] = col; 56 continue; 57 } 58 if(max_r != k) { 59 for(int j = col; j < var + 1; j++) 60 swap(a[k][j], a[max_r][j]); 61 } 62 for(int i = k + 1; i < equ; i++) { 63 if(a[i][col] != 0) { 64 for(int j = col; j < var + 1; j++) { 65 a[i][j] ^= a[k][j]; 66 } 67 } 68 } 69 } 70 for(int i = k; i < equ; i++) { 71 if(a[i][col] != 0) 72 return -1; 73 } 74 // if(k < var) return var - k; 75 for(int i = var - 1; i >= 0; i--) { 76 x[i] = a[i][var]; 77 for(int j = i + 1; j < var; j++) { 78 x[i] ^= (a[i][j] & x[j]); 79 } 80 } 81 return 0; 82 } 83 84 char G[maxn][maxn]; 85 86 int main() { 87 // freopen("in", "r", stdin); 88 int T, _ = 1; 89 scanf("%d", &T); 90 while(T--) { 91 scanf("%d", &var); 92 memset(a, 0, sizeof(a)); 93 memset(x, 0, sizeof(x)); 94 memset(free_x, 0, sizeof(free_x)); 95 for(int i = 0; i < var; i++) { 96 scanf("%s", G[i]); 97 } 98 int cnt = 0; 99 for(int i = 0; i < var; i++) { 100 for(int j = 0; j < var; j++) { 101 if(G[i][j] == 'w') a[cnt][var*var] = 1; 102 cnt++; 103 } 104 } 105 int t = var; 106 var = var * var; 107 equ = var; 108 for(int i = 0; i < t; i++) { 109 for(int j = 0; j < t; j++) { 110 int q = i * t + j; 111 a[q][q] = 1; 112 if(i > 0) a[(i-1)*t+j][q] = 1; 113 if(i < t - 1) a[(i+1)*t+j][q] = 1; 114 if(j > 0) a[i*t+j-1][q] = 1; 115 if(j < t - 1) a[i*t+j+1][q] = 1; 116 } 117 } 118 // for(int i = 0; i < t; i++) { 119 // for(int j = 0; j < t; j++) { 120 // printf("%d ", a[i][j]); 121 // } 122 // printf(" "); 123 // } 124 int v = gauss(); 125 ret = 0; 126 if(v == -1) puts("inf"); 127 else { 128 for(int i = 0; i < var; i++) ret += x[i]; 129 printf("%d ", ret); 130 } 131 } 132 return 0; 133 }