poj 1681（Gauss 消元）

Painter's Problem

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 5875		Accepted: 2825

Description

There is a square wall which is made of n*n small square bricks. Some bricks are white while some bricks are yellow. Bob is a painter and he wants to paint all the bricks yellow. But there is something wrong with Bob's brush. Once he uses this brush to paint brick (i, j), the bricks at (i, j), (i-1, j), (i+1, j), (i, j-1) and (i, j+1) all change their color. Your task is to find the minimum number of bricks Bob should paint in order to make all the bricks yellow.

Input

The first line contains a single integer t (1 <= t <= 20) that indicates the number of test cases. Then follow the t cases. Each test case begins with a line contains an integer n (1 <= n <= 15), representing the size of wall. The next n lines represent the original wall. Each line contains n characters. The j-th character of the i-th line figures out the color of brick at position (i, j). We use a 'w' to express a white brick while a 'y' to express a yellow brick.

Output

For each case, output a line contains the minimum number of bricks Bob should paint. If Bob can't paint all the bricks yellow, print 'inf'.

Sample Input

2
3
yyy
yyy
yyy
5
wwwww
wwwww
wwwww
wwwww
wwwww

Sample Output

0
15

Source

POJ Monthly--2004.06.27 张嘉龄

很明显的异或版Gauss 消元，其中还要枚举出自由变元的取值来确定确定变元的值以查找最小的答案。

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<algorithm>
  5 #define clr(x) memset(x,0,sizeof(x))
  6 #define clrdown(x) memset(x,-1,sizeof(x))
  7 using namespace std;
  8 int A[500][500];
  9 int x[500];
 10 int free_x[500];
 11 int mov[4][2]={0,1,0,-1,1,0,-1,0};
 12 char s[30];
 13 void init(int n);
 14 int Gauss(int n);
 15 int main()
 16 {
 17     int T,n,p;
 18     scanf("%d",&T);
 19     while(T--)
 20     {
 21         scanf("%d",&n);
 22         init(n);
 23         if((p=Gauss(n))==-1)
 24         {
 25             printf("inf
");
 26         }
 27         else
 28         {
 29             printf("%d
",p);
 30         }
 31 
 32     }
 33     return 0;
 34 }
 35 //初始化以及读入操作
 36 void init(int n)
 37 {
 38     clr(A);
 39     for(int i=0;i<n;i++)
 40         for(int j=0;j<n;j++)
 41     {
 42         A[i*n+j][i*n+j]=1;
 43         for(int k=0;k<4;k++)
 44             if(i+mov[k][0]>=0 && i+mov[k][0]<n && j+mov[k][1]>=0 && j+mov[k][1]<n)
 45             {
 46                         A[(i+mov[k][0])*n+j+mov[k][1]][i*n+j]=1;
 47             }
 48     }
 49     for(int i=0;i<n;i++)
 50     {
 51         scanf("%s",s);
 52         for(int j=0;j<n;j++)
 53             if(s[j]=='w')
 54                 A[i*n+j][n*n]=1;
 55     }
 56 /*    for(int i=0;i<n*n;i++)
 57     {
 58         for(int j=0;j<=n*n;j++)
 59             printf("%d ",A[i][j]);
 60         printf("
");
 61     }*/
 62     clr(free_x);
 63     return ;
 64 }
 65 //gauss消元部分
 66 int Gauss(int n)
 67 {
 68     int num=0;
 69     int k,col;
 70     //从第0行0列开始消元
 71     for(k=0,col=0;k<n*n && col<n*n;col++,k++)
 72     {
 73         if(!A[k][col])
 74         {
 75             for(int i=k+1;i<n*n;i++)
 76                 if(A[i][col])
 77                 {
 78                     for(int j=col;j<=n*n;j++)
 79                         swap(A[k][j],A[i][j]);
 80                     break;
 81                 }
 82         }//找k列有最大值的行与之交换（即只要有1）。
 83         if(!A[k][col])
 84         {
 85             k--;
 86             free_x[num++]=col;//记录自由变元的位置
 87             continue;
 88         }//该行全是0,指向当前行下一列并记录自由变元的下标col
 89         for(int i=k+1;i<n*n;i++)
 90             if(A[i][col])
 91                 for(int j=col;j<=n*n;j++)
 92                     A[i][j]=(A[i][j]+A[k][j])%2;
 93     }//消元部分
 94     for(int i=0;i<n*n;i++)
 95 /*    {
 96         for(int j=0;j<=n*n;j++)
 97             printf("%d ",A[i][j]);
 98         printf("
");
 99     }
100     printf("%d %d
",num,k);*/
101     for(int i=k;i<n*n;i++)
102         if(A[i][n*n])
103          return -1;
104     //若k行及之后有（0,0,0,0，……，1）的行则无解，返回-1
105     int p=n*n-k;//p即为自由变元的数量
106     int c,temp,ans,minn=1000000000,index,ct;
107     for( index=0;index<(1<<p);index++)//index从0开始枚举自由变元至1<<p
108     {
109         clrdown(x);
110         ans=0;
111         ct=index;
112         for(int i=0;i<p;ct>>=1,i++)
113             if(ct&1)
114             {
115                 ans++;
116                 x[free_x[i]]=1;
117             }
118             else
119                 x[free_x[i]]=0;
120         //给是自由变元的x[i]赋值
121         for(int i=k-1;i>=0;i--)
122         {
123             c=n*n-1;
124             temp=A[i][col];
125             while(x[c]!=-1)
126             {
127                 if(x[c])
128                     temp=(temp+A[i][c])%2;
129                 c--;
130             }
131             x[c]=temp;
132             if(x[c])
133                 ans++;
134         }
135         if(ans<minn)
136             minn=ans;
137 //        printf("%d %d
",minn,ans);
138     }
139     return minn;
140 }