题目：给一个n*m的矩阵，全部都是由0和1构成的，每次翻转一个点的时候周围上下左右的点也会翻转。现在可以选择点进行翻转，输出每个点翻转次数的矩阵，翻转总次数要最小，如果有多个这样的矩阵输出最小字典序的。
条件：1 每次翻转一个点的时候周围上下左右的点也会翻转
2 如果有多个这样的矩阵输出最小字典序的
翻转问题：这一类问题一般每个位置都只有两种状态。这类问题一般有三个特点：
1 某个位置翻转次数n的效果和n%2的效果是一样，所以一个位置要么翻要么不翻
2 翻转的顺序并不影响结果
3 从第一个位置开始考虑翻转情况，再每次在上一个情况不变的情况下考虑翻转（搜索）
本题思路：如果是要搜索n*m的情况的话，那么2的15*15次方必定会超时，但是如果只枚举第一行2的15次方，然后通过在第一行依次确定剩下的行数的翻转情况。比如某个矩阵第一行枚举完翻转次数后，第三列的数字还是1，那么假定第一行翻转次数不变，要想改变第一行第三列的数字就必须让第二行第三列的数字翻转。最后再检查最后一行是否全部为0。
还使用了状态压缩，枚举第一行的时候用了二进制数，通过第一行按字典序枚举，达到字典序小的优先。
代码：
#include <cstdio> #include <cstdlib> #include <cstring> const int maxn=16; const int inf=0x3f3f3f3f; int n,m,count1=0,min1=1<<30;//最小翻转次数; int bo[maxn][maxn],cur[maxn][maxn];//原矩阵，操作后的矩阵 int op[maxn][maxn],ans[maxn][maxn];//操作次数矩阵和答案矩阵 void turn(int x,int y)//翻转 { cur[x][y]=(cur[x][y]+1)%2; cur[x+1][y]=(cur[x+1][y]+1)%2; cur[x-1][y]=(cur[x-1][y]+1)%2; cur[x][y+1]=(cur[x][y+1]+1)%2; cur[x][y-1]=(cur[x][y-1]+1)%2; } int solve() { memcpy(cur,bo,sizeof(bo));//复制原来的矩阵 for(int i=0;i<m;i++)//根据枚举改变第二行的 { if(op[0][i])//如果第一个没有达成，就反转 { turn(0,i); count1++;//步数++ } } for(int i=1;i<n;i++)//从第二行开始 { for(int j=0;j<m;j++) { if(cur[i-1][j]) { op[i][j]=1; turn(i,j); count1++;//翻转次数++ } } } for(int i=0;i<m;i++) { if(cur[n-1][i]) return 0; } return 1; } int main() { scanf("%d%d",&n,&m);//输入行列 for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { scanf("%d",&bo[i][j]);//输入矩阵 } } for(int i=0;i<(1<<m);i++)//2的15次方可能，第一行，状态压缩 { memset(op,0,sizeof(op)); count1=0; for(int j=0;j<m;j++) { op[0][m-j-1]=i>>j&1;//2的15次方每个数字的，二进制每一个位数，保证了枚举从字典序小的开始 } solve(); if(count1>0&&count1<min1)//翻转总次数最小 { min1=count1; memcpy(ans,op,sizeof(op));//答案矩阵复制 } } if(min1!=(1<<30)) { for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { printf("%d ",ans[i][j]); } printf("\n"); } } else printf("IMPOSSIBLE\n"); return 0; }总结：1 翻转问题是我以前一直都没有想明白，这次终于把它解决了
2 终于又重新开始acm做题了
