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