题意：给一个n*m的矩阵，0表示灯关，1表示开，按下(x,y),那么与他相连和本身的共5个灯翻转，输出翻转次数最少的 字典序最小的方案
分析：非常经典的题，一个灯按两次，相当于没按，那么只要求哪些灯按，哪些灯没按，直接枚举状态有2^(n*m))，太大，接下来我们考虑如何让一个灯翻转，显然相连的四个灯和本身，那么我枚举了第一排的灯是否按，最多只有2^15，那么如果第0行有灯没关，那么第一行相应的就要按，如果关了，下面的就不能按，也就是说，第一行确定了之后，接下来的所有行都确定了，模拟搞就行了，f（i，j)表示被翻转的状态，g表示初始状态，字典序，只要res=ans的时候，比较一下就行了
还有高斯消元法，还没搞
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int maxn=17; const int dx[]={0,0,0,1,-1}; const int dy[]={1,-1,0,0,0}; int g[maxn][maxn],f[maxn][maxn],t[maxn][maxn],a[maxn][maxn]; int m,n; void siv(int x,int y){ for(int i=0;i<5;i++){ int nx=x+dx[i]; int ny=y+dy[i]; if(nx<0||nx>=n||ny<0||ny>=m) continue; f[nx][ny]^=1; } } bool cmp(){ for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(a[i][j]>t[i][j]) return true; else if(a[i][j]<t[i][j]) return false; return false; } int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&g[i][j]); int tmp=(1<<m),ans=15*15; for(int i=0;i<tmp;i++){ int res=0; memset(f,0,sizeof(f)); memset(t,0,sizeof(t)); for(int k=0;k<m;k++) if(i&(1<<k)){ siv(0,k); t[0][k]=1; res++; } for(int k=1;k<n;k++) for(int j=0;j<m;j++) if((f[k-1][j]+g[k-1][j])%2==1){ siv(k,j); t[k][j]=1; res++; } for(int j=0;j<m;j++) if((f[n-1][j]+g[n-1][j])%2!=0) res=15*15; if(res<ans||(res==ans&&cmp())){ for(int k=0;k<n;k++) for(int j=0;j<m;j++) a[k][j]=t[k][j]; ans=res; } } if(ans==15*15){ puts("IMPOSSIBLE"); continue; } for(int i=0;i<n;i++){ printf("%d",a[i][0]); for(int j=1;j<m;j++) printf(" %d",a[i][j]); puts(""); } } return 0; }