POJ 1753 Flip Game (高斯消元)

题目地址：POJ 1753

第三次做这道题了。第一次是刚学搜索的时候做的，第二次是刚学状态压缩枚举的时候做的，这次是刚学高斯消元、、每次都做得很艰辛。。目测这题应该没了别的方法了吧。。。。。。

这题除了高斯消元外还需要枚举变元，方法是状态压缩枚举，然后返回去迭代解方程。

代码如下：

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-6;
int mp[5][5], a[20][20], free_num, free_x[20], x[20];
int jx[]={0,0,1,-1};
int jy[]={1,-1,0,0};
int gauss()
{
        int i, j, k, free_num=0, h, tmp, t;
        for(i=0,j=0;i<16&&j<16;i++,j++){
                if(a[i][j]==0){
                        for(k=i+1;k<16;k++){
                                if(a[k][j]) break;
                        }
                        if(k==16){
                                free_x[free_num++]=j;
                                i--;
                                continue ;
                        }
                        for(h=j;h<17;h++){
                                swap(a[i][h],a[k][h]);
                        }
                }
                for(k=i+1;k<16;k++){
                        if(a[k][j]){
                                for(h=j;h<17;h++){
                                        a[k][h]^=a[i][h];
                                }
                        }
                }
        }
        tmp=i;
        for(j=i;j<16;j++){
                if(a[j][16]) return INF;
        }
        int ans=INF;
        int tot=1<<free_num;
        //printf("%d\n",free_num);
        for(i=0;i<tot;i++){
                int cnt=0;
                for(j=0;j<free_num;j++){
                        if(i&(1<<j)){
                                x[free_x[j]]=1;
                                cnt++;
                        }
                        else{
                                x[free_x[j]]=0;
                        }
                }
                //printf("%d\n",cnt);
                for(j=tmp-1;j>=0;j--){
                        t=0;
                        while(a[j][t]==0) t++;
                        x[t]=a[j][16];
                        for(k=t+1;k<16;k++){
                                if(a[j][k])  x[t]^=x[k];
                        }
                        cnt+=x[t];
                }
                //printf("%d\n",cnt);
                ans=min(ans,cnt);
        }
        return ans;
}
void init()
{
        memset(a,0,sizeof(a));
        for(int i=0;i<4;i++){
                for(int j=0;j<4;j++){
                        for(int k=0;k<4;k++){
                                int x=i+jx[k];
                                int y=j+jy[k];
                                if(x>=0&&x<4&&y>=0&&y<4){
                                        a[4*i+j][4*x+y]=1;
                                }
                        }
                        a[4*i+j][4*i+j]=1;
                }
        }
}
int main()
{
        char s[6];
        int i, j, k, x, y, ans1, ans2;
        for(i=0;i<4;i++){
                scanf("%s",s);
                for(j=0;j<4;j++){
                        if(s[j]=='b') mp[i][j]=0;
                        else mp[i][j]=1;
                }
        }
        init();
        for(i=0;i<4;i++){
                for(j=0;j<4;j++){
                        a[4*i+j][4*4]=mp[i][j];
                }
        }
        ans1=gauss();
        init();
        for(i=0;i<4;i++){
                for(j=0;j<4;j++){
                        a[4*i+j][4*4]=1-mp[i][j];
                }
        }
        ans2=gauss();
        if(ans1==INF&&ans2==INF){
                printf("Impossible\n");
        }
        else{
                printf("%d\n",min(ans1,ans2));
        }
        return 0;
}