POJ 1681 高斯消元 枚举自由变元

题目和poj1222差不多，但是解法有一定区别，1222只要求出任意一解，而本题需要求出最少翻转次数。所以需要枚举自由变元，变元数量为n，则枚举的次数为1<<n次

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=500;
char s[maxn][maxn];
int a[maxn][maxn],x[maxn],fre[maxn];
const int INF=1e9;

void debug(int n)
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
            printf("%d ",a[i][j]);
        printf(" %d
",a[i][n]);
    }
}

void init(int n)
{
    int dx[]= {0,0,-1,0,1};
    int dy[]= {0,-1,0,1,0};
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            for(int k=0; k<5; k++)
            {
                int x=i+dx[k];
                int y=j+dy[k];
                if(x>=0 && x<n && y>=0 && y<n)
                    a[i*n+j][x*n+y]=1;
            }
        }
    }
}

int Guass(int equ,int var)
{
    int k,col,num=0;
    for(k=0,col=0; k<equ && col<var; k++,col++)
    {
        int rr=k;
        for(int i=k; i<equ; i++)
            if(a[i][col]!=0)
            {
                rr=i;
                break;
            }
        if(rr!=k)
            for(int j=col; j<var+1; j++)
                swap(a[k][j],a[rr][j]);
        if(a[k][col]==0)
        {
            k--;
            fre[num++]=col;
            continue;
        }
        for(int i=k+1; i<equ; i++)
        {
            if(a[i][col]==0) continue;
            for(int j=col; j<var+1; j++)
                a[i][j]^=a[k][j];
        }
    }
    //debug(equ);
    for(int i=k; i<equ; i++)
        if(a[i][var]!=0) return -1;
    int sta=1<<(var-k);//自由变元有var-k个
    int res=INF;
    for(int i=0; i<sta; i++) //枚举所有变元
    {
        int cnt=0;
        int index=i;
        for(int j=0; j<num; j++)
        {
            x[fre[j]]=(index&1);
            if(x[fre[j]]) cnt++;
            index>>=1;
        }
        for(int row=k-1; row>=0; row--)
        {
            x[row]=a[row][var];
            for(col=row+1; col<var; col++)
                x[row]^=(a[row][col]*x[col]);
            if(x[row])cnt++;
        }
        res=min(cnt,res);
    }
    return res;
}

int main()
{
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(a,0,sizeof(a));
        memset(fre,1,sizeof(fre));
        int n;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%s",s[i]);
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                a[i*n+j][n*n]=(s[i][j]=='y'? 0:1);
        init(n);
        int ans=Guass(n*n,n*n);
        if(ans==-1)
        {
            printf("inf
");
            continue;
        }
        printf("%d
",ans);
    }
    return 0;
}