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.
![poj 1681（Gauss 消元）-LMLPHP]( "poj 1681（Gauss 消元）-LMLPHP")
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
很明显的异或版Gauss 消元，其中还要枚举出自由变元的取值来确定确定变元的值以查找最小的答案。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define clr(x) memset(x,0,sizeof(x))
#define clrdown(x) memset(x,-1,sizeof(x))
using namespace std;
int A[][];
int x[];
int free_x[];
int mov[][]={,,,-,,,-,};
char s[];
void init(int n);
int Gauss(int n);
int main()
{
int T,n,p;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
init(n);
if((p=Gauss(n))==-)
{
printf("inf\n");
}
else
{
printf("%d\n",p);
} }
return ;
}
//初始化以及读入操作
void init(int n)
{
clr(A);
for(int i=;i<n;i++)
for(int j=;j<n;j++)
{
A[i*n+j][i*n+j]=;
for(int k=;k<;k++)
if(i+mov[k][]>= && i+mov[k][]<n && j+mov[k][]>= && j+mov[k][]<n)
{
A[(i+mov[k][])*n+j+mov[k][]][i*n+j]=;
}
}
for(int i=;i<n;i++)
{
scanf("%s",s);
for(int j=;j<n;j++)
if(s[j]=='w')
A[i*n+j][n*n]=;
}
/* for(int i=0;i<n*n;i++)
{
for(int j=0;j<=n*n;j++)
printf("%d ",A[i][j]);
printf("\n");
}*/
clr(free_x);
return ;
}
//gauss消元部分
int Gauss(int n)
{
int num=;
int k,col;
//从第0行0列开始消元
for(k=,col=;k<n*n && col<n*n;col++,k++)
{
if(!A[k][col])
{
for(int i=k+;i<n*n;i++)
if(A[i][col])
{
for(int j=col;j<=n*n;j++)
swap(A[k][j],A[i][j]);
break;
}
}//找k列有最大值的行与之交换（即只要有1）。
if(!A[k][col])
{
k--;
free_x[num++]=col;//记录自由变元的位置
continue;
}//该行全是0,指向当前行下一列并记录自由变元的下标col
for(int i=k+;i<n*n;i++)
if(A[i][col])
for(int j=col;j<=n*n;j++)
A[i][j]=(A[i][j]+A[k][j])%;
}//消元部分
for(int i=;i<n*n;i++)
/* {
for(int j=0;j<=n*n;j++)
printf("%d ",A[i][j]);
printf("\n");
}
printf("%d %d\n",num,k);*/
for(int i=k;i<n*n;i++)
if(A[i][n*n])
return -;
//若k行及之后有（0,0,0,0，……，1）的行则无解，返回-1
int p=n*n-k;//p即为自由变元的数量
int c,temp,ans,minn=,index,ct;
for( index=;index<(<<p);index++)//index从0开始枚举自由变元至1<<p
{
clrdown(x);
ans=;
ct=index;
for(int i=;i<p;ct>>=,i++)
if(ct&)
{
ans++;
x[free_x[i]]=;
}
else
x[free_x[i]]=;
//给是自由变元的x[i]赋值
for(int i=k-;i>=;i--)
{
c=n*n-;
temp=A[i][col];
while(x[c]!=-)
{
if(x[c])
temp=(temp+A[i][c])%;
c--;
}
x[c]=temp;
if(x[c])
ans++;
}
if(ans<minn)
minn=ans;
// printf("%d %d\n",minn,ans);
}
return minn;
}