[Gauss]POJ1753 Flip Game

题意：给4×4的棋盘的初始状态，b代表黑，w代表白。

要求变成全黑或者全白 最少需要几步。

简单的做法 可以暴搜 状压bfs 不再赘述

主要学习Gauss做法

同样是01方程组 用异或解

注意全黑或全白都可以

即 bbbb        wwww

bbbb        wwww

　 bbbb        wwww

　 bbbb        wwww      这两种的步数步数都是0.

因此我的做法是 列两个方程组分别求最小步数，再取最小值

 int a[][];  // 增广矩阵

 int b[][];

 int x[];  // 解

 int free_x[]; // 标记是否为自由未知量

 int n;

 void debug()

 {

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

     {

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

             printf("%d ", a[i0][j0]);

         printf("\n");

     }

 }

 int Gauss(int n, int m) // n个方程 m个未知数 即 n行m+1列

 {

     //转换为阶梯形式

     int col=, k, num=;

     for(k=;k<n && col<m;k++, col++)

     {//枚举行

         int max_r=k;

         for(int i=k+;i<n;i++)//找到第col列元素绝对值最大的那行与第k行交换

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

                 max_r=i;

         if(max_r!=k)// 与第k行交换

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

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

         if(!a[k][col])// 说明该col列第k行以下全是0了

         {

             k--;

             free_x[num++]=col;

             continue;

         }

         for(int i=k+;i<n;i++)// 枚举要删除的行

             if(a[i][col])

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

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

     }

 //    debug();

 //    printf("%d %d\n", col, k);

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

         if(a[i][col])

             return -; // 无解

 //    if(k<m)   //m-k为自由未知量个数

 //    {

         int stat=<<(m-k);

         int ans=INT_MAX;

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

         {

             int cnt=;

             for(int j=;j<m-k;j++)

                 if(i&(<<j))

                 {

                     x[free_x[j]]=;

                     cnt++;

                 }

                 else

                     x[free_x[j]]=;

             for(int j=k-;j>=;j--)

             {

                 int tmp;

                 for(tmp=j;tmp<m;tmp++)

                     if(a[j][tmp])

                         break;

                 x[tmp]=a[j][m];

                 for(int l=tmp+;l<m;l++)

                     if(a[j][l])

                         x[tmp]^=x[l];

                 cnt+=x[tmp];

             }

             if(cnt<ans)

                 ans=cnt;

         }

         return ans;

 //    }

 //    //  唯一解 回代

 //    for(int i=m-1;i>=0;i--)

 //    {

 //        x[i]=a[i][m];

 //        for(int j=i+1;j<m;j++)

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

 //    }

 //    int ans=0;

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

 //        ans+=x[i];

 //    return ans;

 }

 void init()

 {

     n=;

     memset(a, , sizeof(a));

     memset(x, , sizeof(x));

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

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

         {

             int t=i*n+j;

             a[t][t]=;

             if(i>)

                 a[(i-)*n+j][t]=;

             if(i<n-)

                 a[(i+)*n+j][t]=;

             if(j>)

                 a[i*n+j-][t]=;

             if(j<n-)

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

         }

 }

 int main()

 {

     char ch;

     while(cin>>ch)

     {

         init();

         a[][]=(ch=='b');

         b[][]=(ch=='w');

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

         {

             cin>>ch;

             a[i][n*n]=(ch=='b');

             b[i][n*n]=(ch=='w');

         }

         int t=Gauss(n*n, n*n);

         if(t==-)

         {

             printf("Impossible\n");

             continue ;

         }

         init();

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

             a[i][]=b[i][];

         int tt=Gauss(n*n, n*n);

         printf("%d\n", min(t, tt));

     }

     return ;

 }

POJ 1753