题意：给定一个4*4的矩阵，有两种颜色，每次反转一个颜色会反转他自身以及上下左右的颜色，问把他们全变成一种颜色的最少步数。
题解：4*4的矩阵打表可知一共有四个自由变元，枚举变元求最小解即可。
代码：
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> #include <vector> #include <map> #include <ctime> using namespace std; const int maxn=300; //有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var int equ,var; int a[maxn][maxn]; //增广矩阵 int x[maxn]; //解集 int free_x[maxn];//用来存储自由变元（多解枚举自由变元可以使用） int free_num;//自由变元的个数 //返回值为-1表示无解，为0是唯一解，否则返回自由变元个数 int gauss() { int max_r,col,k; free_num=0; for(k=0,col=0; k<equ&&col<var; k++,col++) { max_r=k; for(int i=k+1; i<equ; i++) if(abs(a[i][col])>abs(a[max_r][col])) max_r=i; if(!a[max_r][col]) { k--; free_x[free_num++]=col; continue; } if(max_r!=k) for(int j=col; j<var+1; j++) swap(a[k][j],a[max_r][j]); for(int i=k+1; i<equ; i++) { if(a[i][col]) { for(int j=col; j<var+1; j++) a[i][j]^=a[k][j]; } } } for(int i=k; i<equ; i++) if(a[i][col]) return -1; if(k<var) return var-k; for(int i=var-1; i>=0; i--) { x[i]=a[i][var]; for(int j=i+1; j<var; j++) x[i]^=(a[i][j]&&x[j]); } return 0; } int n; void init() { memset(a,0,sizeof(a)); memset(x,0,sizeof(x)); equ=n*n; var=n*n; 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[(i-1)*n+j][t]=1; if(i<n-1) a[(i+1)*n+j][t]=1; if(j>0) a[i*n+j-1][t]=1; if(j<n-1) a[i*n+j+1][t]=1; } } int solve() { int t=gauss(); if(t==-1) { return -1; } else if(t==0) { int ans=0; for(int i=0; i<n*n; i++) ans+=x[i]; return ans; } else { //枚举自由变元 int ans=0x3f3f3f3f; int tot=(1<<t); for(int i=0; i<tot; i++) { int cnt=0; for(int j=0; j<t; j++) { if(i&(1<<j)) //注意不是&& { x[free_x[j]]=1; cnt++; } else x[free_x[j]]=0; } for(int j=var-t-1; j>=0; j--) { int idx; for(idx=j; idx<var; idx++) if(a[j][idx]) break; x[idx]=a[j][var]; for(int l=idx+1; l<var; l++) if(a[j][l]) x[idx]^=x[l]; cnt+=x[idx]; } ans=min(ans,cnt); } return ans; } } char str[30][30]; int main() { n=4; for(int i=0;i<4;i++) scanf("%s",str[i]); init(); for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) { if(str[i][j] == 'b')a[i*4+j][16] = 0; else a[i*4+j][16] = 1; } int ans1 = solve(); init(); for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) { if(str[i][j] == 'b')a[i*4+j][16] = 1; else a[i*4+j][16] = 0; } int ans2 = solve(); if(ans1 == -1 && ans2 == -1) printf("Impossible "); else printf("%d ",min(ans1,ans2)); return 0; }