poj 1753 Flip Game
题意:和poj 1681一样，4*4的01矩阵输入为b|w,关联也是周围四个方向。只是最优解(操作个数最少)是只要最终同色就行，没有确定哪个是1.
此题确实可以直接枚举第一行，
思路:原本认为弄成*变元的个数之后，全部变为0和全部变为1的操作数之和就是var - ret(*变元的个数)，这样只需要调用Gauss一次即可。但是还有一个前提就是认为最有解就是*变元就认为是没操作，但是这一题与1681Painter's Problem 不同，一定要枚举*变元来确定其他维度的变量。所以还是要两次调用Gauss().
(Gauss-Jordan elimination)：
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define inf 0x3f3f3f3f int dir[2][4] = {{0,1,0,-1},{1,0,-1,0}}; int a[20][20]; int equ,var; int x[20],free_var[20]; void debug() { puts("********"); int i,j; rep0(i,0,equ){ rep1(j,0,var) cout<<a[i][j]<<" "; cout<<endl; }puts("********"); } int Gauss() { int i,j,k,row,col,cnt = 0; for(row = 0,col = 0;row < equ && col < var;row++,col++){ int mx = row; rep0(j,row+1,equ) if(abs(a[j][col]) > abs(a[mx][col])) mx = j; if(a[mx][col] == 0){ row--; // 行不变；不能通过这里记录*变元的个数，只能记录没用的col free_var[cnt++] = col;//记录*变元的标号； continue; } if(mx != row) rep1(k,col,var) swap(a[row][k],a[mx][k]); rep0(j,row+1,equ){ if(a[j][col]){ rep1(k,col,var) a[j][k] ^= a[row][k]; } } } //debug(); rep0(i,row,equ) if(a[i][var] != 0) return -1; //无解 //枚举*变元,row表示有用的方程数方程,但是要在判断出有解的前提下才能说有多组解； //if(row < var) return var - row; //当不需要枚举时，直接返回*变元的个数 int ans = inf,tot = 1 <<(var - row); rep0(i,0,tot){ int cnt = 0,tmp = i; rep0(j,0,var - row){ x[free_var[j]] = (tmp&1); if(x[free_var[j]]) cnt++;//** tmp >>= 1; } rep_1(i,row-1,0){ x[i] = a[i][var];//现在赋为a[i][var],若为*变元之后还是会等于0，不会重复计算； rep0(j,i+1,equ){ x[i] ^= (a[i][j] && x[j]); //第j个灯会影响到第i盏灯，同时第j盏灯也会亮 } if(x[i]) cnt++; } ans = min(ans,cnt); } return ans; } void init(int n) { MS0(x);MS0(a);MS0(free_var); int i,j,k; rep0(i,0,n) rep0(j,0,n){ int id = i*n+j; a[id][id] = 1; rep0(k,0,4){ int nx = i + dir[0][k] ,ny = j + dir[1][k]; if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue; a[nx*n+ny][id] = 1; } } } int tmp[20]; int main() { //freopen("in.txt","r",stdin); //freopen("data2.txt","w",stdout); int n = 4,i,id = 0; equ = var = n*n; rep0(i,0,var){ char c = getchar(); if(c == 'w') id |= (1<<i);//使用状压来存储状态。 else if(c != 'b') i--; } init(n); rep0(i,0,var){ a[i][var] = (id >> i)& 1; } //debug(); int ans = inf; rep0(j,0,2){ int ret = Gauss(); if(ret == -1) continue; ans = min(ans,ret); if(j == 2) break; init(n); rep0(i,0,var){ a[i][var] = (id & 1)^1; id >>= 1; } } if(ans == inf) puts("Impossible"); else printf("%d ",ans); return 0; }
dfs枚举1:枚举全部的格子状态，即1<<16范围；750ms..
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) int dir[2][4] = {{0,1,0,-1},{1,0,-1,0}}; #define inf 0x3f3f3f3f int a[5][5],b[5][5]; int check(int s,int id) { int cnt = 0; rep0(i,0,4) rep0(j,0,4) b[i][j] = a[i][j]; rep0(i,0,16){ if(s&(1<<i)){ cnt++; int x = i/4,y = i % 4; b[x][y] ^= 1; rep0(j,0,4){ int nx = x + dir[0][j],ny = y + dir[1][j]; if(nx >= 0 && nx < 4 && ny >= 0 && ny < 4) b[nx][ny] ^= 1; } } } rep0(i,0,4) rep0(j,0,4) if(b[i][j] != id ) return inf; return cnt; } int solve(int id) { int i,j,tot = 1<<16,ans = inf; rep0(i,0,tot){ ans = min(ans,check(i,id)); } return ans; } int main() { //freopen("in.txt","r",stdin); //freopen("data2.txt","w",stdout); int n = 4; char c[5]; rep0(i,0,4){ scanf("%s",c); rep0(j,0,4) if(c[j] == 'w') a[i][j] = 1; else a[i][j] = 0; } int ans = inf; ans = min(ans,solve(0)); ans = min(ans,solve(1)); if(ans == inf) puts("Impossible"); else printf("%d ",ans); return 0; }