POJ 1681 Painter's Problem（高斯消元+枚举自由变元）

http://poj.org/problem?id=1681

题意：
有一块只有黄白颜色的n*n的板子，每次刷一块格子时，上下左右都会改变颜色，求最少刷几次可以使得全部变成黄色。

思路：

这道题目也就是要处理自由变元，如果自由变元为0，那么刷法是唯一的，如果有多个自由变元，那么可以有多种刷法，需要枚举处理。

借鉴了kuangbin大神的高斯消元模板，写得真的是好。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn =  + ;

 int n;

 int equ,var;  //equ个方程，var个变元

 int x[maxn]; //解集

 int a[maxn][maxn]; //矩阵

 int free_x[maxn];  //存储自由变元

 int free_num;      //自由变元的个数

 //返回值为-1表示无解，为0表示唯一解，否则返回自由变元个数

 int Gauss()

 {

     int max_r,col,k;

     free_num=;

     for(k=,col=; k<equ && col<var; k++,col++)

     {

         max_r=k;

         for(int i=k+;i<equ;i++)

         {

             if(abs(a[i][col])>abs(a[max_r][col]))

                 max_r=i;

         }

         if(a[max_r][col]==)

         {

             k--;

             free_x[free_num++]=col;  //这个是自由变元;

             continue;

         }

         if(max_r!=k)

         {

             for(int j=col; j<var+; j++)

                 swap(a[k][j],a[max_r][j]);

         }

         for(int i=k+;i<equ;i++)

         {

             if(a[i][col]!=)

             {

                 for(int j=col;j<var+;j++)

                     a[i][j]^=a[k][j];

             }

         }

     }

     for(int i=k;i<equ;i++)

         if(a[i][col]!=)  return -;  //无解

     if(k<var)  return var-k;          //有多解时返回自由变元个数

     //唯一解，回代

     for(int i=var-; i>= ;i--)

     {

         x[i]=a[i][var];

         for(int j=i+; j<var; j++)

             x[i]^=(a[i][j] && x[j]);

     }

     return ;

 }

 void print(int t)

 {

     if(t==-)  puts("inf");

     else if(t==)

     {

         int ans=;

         for(int i=;i<n*n;i++)   ans+=x[i];

         printf("%d\n",ans);

     }

     else

     {

         //枚举自由变元

         int ans=INF;

         for(int i=;i<(<<t);i++)

         {

             int cnt=;

             for(int j=;j<t;j++)

             {

                 if(i&(<<j))

                 {

                     x[free_x[j]]=;

                     cnt++;

                 }

                 else x[free_x[j]]=;

             }

             for(int j=var-t-;j>=;j--)

             {

                 int idx;

                 for(idx=j; idx<var; idx++)

                     if(a[j][idx])  break;

                 x[idx]=a[j][var];

                 for(int l=idx+; l<var; l++)

                     if(a[j][l])  x[idx]^=x[l];

                 cnt+=x[idx];

             }

             ans=min(ans,cnt);

         }

         printf("%d\n",ans);

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         memset(a,,sizeof(a));

         for(int i=;i<n*n;i++)

         {

             a[i][i]=;

             if(i/n)      a[i-n][i]=;

             if(i/n<n-)  a[i+n][i]=;

             if(i%n)      a[i-][i]=;

             if(i%n<n-)  a[i+][i]=;

         }

         char s[];

         for(int i=;i<n;i++)

         {

             scanf("%s",s);

             for(int j=;j<n;j++)

             {

                 if(s[j]=='y')  a[i*n+j][n*n]=;

                 else a[i*n+j][n*n]=;

             }

         }

         memset(x,,sizeof(x));

         equ=var=n*n;

         print(Gauss());

     }

     return ;

 }