题目链接: http://poj.org/problem?id=1753
题目大意：一堆格子，或白或白。每次可以把一个改变一个格子颜色，其上下左右四个格子颜色也改变。问最后使格子全部白或全部黑，求最小改变的格子树。
解题思路：
与POJ 1681 类似。不过这次是或黑或白，要初始化两次相反的解向量，
进行两次高斯消元，取其中小的值。
特殊的是，本题中有*变元的存在，也就是说这个格子可黑可白，对结果没有影响。
这时候就会存在无穷解。其实POJ 1681也可能存在*变元，不过数据略水，没处理也能A掉。
如果不对*变元处理，那么我们只会处理一种解，所以某些情况答案是不对的。
*变元的处理变化参照模板，渣渣暂时看不懂。
#include "cstdio"
#include "iostream"
#include "cstring"
using namespace std;
int ratio[][],mat[],freex[],x[],dir[][]={,,-,,,,,-,,},T,n;
void reset()
{
for(int i=;i<n;i++)
for(int j=;j<n;j++)
for(int k=;k<;k++)
{
int x=i+dir[k][],y=j+dir[k][];
if(x>=&&y>=&&x<n&&y<n) ratio[i*n+j][x*n+y]=;
}
}
int gauss()
{
int i,j,k,num=;
for(i=,j=;i<n*n&&j<n*n;i++,j++)
{
k=i;
for(;k<n*n;k++)
if(ratio[k][j]) break;
for(int t=j;t<=n*n;t++)
if(i!=k) swap(ratio[i][t],ratio[k][t]);
if(!ratio[i][j]) {i--;freex[num++]=j;continue;}
for(k=i+;k<n*n;k++)
{
if(ratio[k][j])
for(int t=j;t<=n*n;t++)
ratio[k][t]^=ratio[i][t];
}
}
k=i;
for(i=k; i<n*n; i++)
if(ratio[i][n*n]) return -;
int bit=<<(n*n-k),ans=0x3f3f3f3f;
for(int t=;t<bit;t++)
{
int cnt=,index=t;
for(j=;j<n*n-k;j++)
{
x[freex[j]]=(index&);
if(x[freex[j]]) cnt++;
index>>=;
}
for(i=k-; i>=; i--)
{
int tmp=ratio[i][n*n];
for(j=i+; j<n*n; j++)
if(ratio[i][j]) tmp^=x[j];
x[i]=tmp;
if(x[i]) cnt++;
}
ans=min(ans,cnt);
}
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
char c[];n=;
int ans=0x3f3f3f3f;
reset();
for(int i=; i<n; i++)
{
scanf("%s",&c);
for(int j=;j<n;j++)
{
if(c[j]=='w') {ratio[i*+j][n*n]=;mat[i*+j]=;}
if(c[j]=='b') {ratio[i*+j][n*n]=;mat[i*+j]=;}
}
}
int ok=gauss();
if(ok!=-) ans=min(ans,ok);
memset(ratio,,sizeof(ratio));
memset(freex,,sizeof(freex));
memset(x,,sizeof(x));
for(int i=;i<n*n;i++) ratio[i][n*n]=mat[i];
reset();
ok=gauss();
if(ok!=-) ans=min(ans,ok);
if(ans==0x3f3f3f3f) printf("Impossible\n");
else printf("%d\n",ans); }
| 13602643 | neopenx | 1753 | Accepted | 160K | 16MS | C++ | 2170B | 2014-11-05 18:35:15 |