pku_1753_Flip Game--Gauss+Dfs
//Name: pku_1753_Flip Game //Author: longxiaozhi http://hi.baidu.com/xiehuixb/blog/item/9ce25f10ee8a2e77ca80c4d1. //Root: 和前面的pku1681一個意思,但是,測試數據加強了!這個題目需要考慮自由元!!也就是我以前的gauss的所在, //這個問題一直困擾了我兩天天。以前的題目的測試數據好像并沒有考慮這一點,所以可以水果去,但是這個題目就不行啦。 //但是,還是可以用gauss的算法解決的。如果不存在自由變元,那么說明原方程組只有一組解,也就是我們要求的; //如果存在自由變元,則說明我們求道的方程的解只是其中的一種情況,但不一定是最優的。 //一次我們還要考慮自由變元因為我們求出來的知識滿足條件的一種解,并不是這里要求的最優解。 //我們要考慮自由變元的取值: //每個自由元我們都枚舉她的值(或)讓后進行一次深搜就可以把自由元的情況加進去,正如xiehui博客里寫的一樣。 #include <iostream> #include <string.h> using namespace std; #define eps 1e-10 #define fabs(x) ((x)>0?(x):-(x)) #define zero(x) (fabs(x) < eps) const int maxn = 16; int a[maxn][maxn+1], b[maxn][maxn+1]; int n, m, ans; const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; inline int isBound(int a, int b) { return a < 0 || a >= m || b < 0 || b >= m; } void pmat(int a[][maxn+1]) { for (int i = 0, j; i < n; i++) { for (j = 0; j < n; j++) printf("%d ", a[i][j]); printf("%d\n", a[i][j]); } } void pans(int a[][maxn+1]) { for (int i = 0; i < n; i++) printf((i+1)%m ? "%d ":"%d\n", a[i][n]); } int gans(int a[][maxn+1]) { int i, j, ret = a[n-1][n]; for (i = n-2; i >= 0; i--) { for (j = i+1; j < n; j++) a[i][n] ^= a[i][j] && a[j][n]; ret += b[i][n]; } return ret; } void dfs(int p, int k) { if (p == k) { memcpy(b, a, sizeof(b)); int ret = gans(b); if (ret < ans) ans = ret; return; } a[p][n] = 1; dfs(p-1, k); a[p][n] = 0; dfs(p-1, k); }
int getRow(int p, int q, int &row) { for (int i = p; i < n; i++) if (!zero(a[i][q])) return a[row=i][q]; return row = 0; } void swapRow(int i, int row, int q) { for (int k = q; k <= n; k++) swap(a[i][k], a[row][k]); } int gauss() { int i = 0, j = -1, k, p, q, ret, row; while(i < n && ++j < n) { ret = getRow(i, j, row); if (zero(ret)) continue; if (row != i) swapRow(i, row, j); for (p = i + 1; p < n; p++) if (a[p][j]) for (q = j; q <= n; q++) a[p][q] ^= a[i][q]; ++i; }pmat(a); for (k = i; k < n; k++) if (a[k][n]) return -1; dfs(n-1, i-1); } int main() { //freopen("in.in", "r", stdin); int i, j, k, x, y, p, q; char s[5][5]; n = 16; m = 4; for (i = 0; i < m; i++) { scanf("%s", s[i]); for (j = 0; j < m; j++) { a[i*m+j][n] = s[i][j] == 'b'; a[i*m+j][i*m+j] = 1; for (k = 0; k < 4; k++) { x = i + dir[k][0]; y = j + dir[k][1]; if (isBound(x, y)) continue; a[i*m+j][x*m+y] = 1; } } } ans = 1 << 20; p = gauss(); // printf("p = %d\n", p); memset(a, 0, sizeof(a)); for (i = 0; i < m; i++) { for (j = 0; j < m; j++) { a[i*m+j][n] = s[i][j] == 'w'; a[i*m+j][i*m+j] = 1; for (k = 0; k < 4; k++) { x = i + dir[k][0]; y = j + dir[k][1]; if (isBound(x, y)) continue; a[i*m+j][x*m+y] = 1; } } } ans = 1 << 20; q = gauss(); // printf("q = %d\n", q); if (p == -1 && q == -1) puts("Impossible"); else if (p == -1) printf("%d\n", q);ac else if (q == -1) printf("%d\n", p); else printf("%d\n", p <= q ? p:q); return 0; } |