题目链接:https://vjudge.net/problem/POJ-1681
题意:类似于poj1222,有n×n的01矩阵,翻转一个点会翻转其上下左右包括自己的点,求最少翻转多少点能使得矩阵全0。
思路:
同样的可以枚举第一行的状态,这里不说了。
用高斯消元法来解这道题,每个点的状态表示一个变量,那么有n*n个方程,n*n个变量的方程组,用高斯消元法来解,可能存在无解,唯一解,多解的情况。多解的时候要枚举自由变元的状态。
AC代码:
/* poj1681 开关问题,高斯消元法解异或方程组 求最少要翻转的开关使得矩阵全0 存在无解,唯一解,多解的情况 多解时要枚举自由变元的状态 */ #include<cstdio> #include<algorithm> #include<cmath> #include<cstdlib> #include<cstring> using namespace std; const int maxn=250; const int inf=0x3f3f3f3f; int T,n,equ,var,a[maxn][maxn],x[maxn],free_xx[maxn]; int ans; char s[20]; void init(){ //初始化 memset(a,0,sizeof(a)); for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ int t=i*n+j; a[t][t]=1; if(i>0) a[t][(i-1)*n+j]=1; if(i<n-1) a[t][(i+1)*n+j]=1; if(j>0) a[t][i*n+j-1]=1; if(j<n-1) a[t][i*n+j+1]=1; } } } int Gauss(){ int r=0,cnt=0; //cnt表示自由变元个数 for(int c=0;r<equ&&c<var;++r,++c){ int Maxr=r; for(int i=r+1;i<equ;++i) if(abs(a[i][c])>abs(a[Maxr][c])) Maxr=i; if(Maxr!=r){ for(int i=c;i<var+1;++i) swap(a[Maxr][i],a[r][i]); } if(!a[r][c]){ --r; free_xx[cnt++]=c; continue; } for(int i=r+1;i<equ;++i){ if(!a[i][c]) continue; for(int j=c;j<var+1;++j) a[i][j]^=a[r][j]; } } for(int i=r;i<equ;++i) if(a[i][var]) return -1; //无解 return var-r; //返回自由变元的个数,cnt=var-r } int solve(int t){ ans=inf; for(int i=0;i<(1<<t);++i){ //枚举自由变元的状态 int cnt=0; //要翻转的个数 memset(x,0,sizeof(x)); for(int j=0;j<t;++j){ if((i>>j)&1){ ++cnt; x[free_xx[j]]=1; } } for(int j=var-t-1;j>=0;--j){ int tmp=a[j][var],tp,ok=1; for(int k=j;k<var;++k){ if(!a[j][k]) continue; if(ok){ //找主元 ok=0; tp=k; } else{ tmp^=x[k]; } } x[tp]=tmp; cnt+=x[tp]; } ans=min(ans,cnt); //取最小 } return ans; } int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); init(); equ=var=n*n; for(int i=0;i<n;++i){ scanf("%s",s); for(int j=0;j<n;++j) if(s[j]=='y') a[i*n+j][n*n]=0; else a[i*n+j][n*n]=1; } int t=Gauss(); if(t==-1) printf("inf\n"); else printf("%d\n",solve(t)); } return 0; }