题意：有一个M*N的棋盘，每一个格子只有两种状态0或1，每次可以选择一个格子执行翻转操作，并且与该格子相邻的4个格子都会被翻转，求将所有格子都翻转成0所需要的最小操作数，若有多种方案，输出字典序最小的方案数。
思路：枚举第一行的状态，深搜接下来每行。此题由上往下搜，所以直接搜四个方向就可以，当前格子状态和周围四个+本身有关。每次记录翻转的最小步数，此题只要步数最小就可以AC。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <sstream> 5 #include <algorithm> 6 #include <list> 7 #include <map> 8 #include <vector> 9 #include <queue> 10 #include <stack> 11 #include <cmath> 12 #include <cstdlib> 13 #include <memory.h> 14 #define clc(a,b) memset(a,b,sizeof(a)) 15 using namespace std; 16 const int maxn=100000; 17 const int inf=0x3f3f3f3f; 18 int n,m; 19 int a[20][20]; 20 int flip[20][20]; 21 int p[20][20]; 22 int dir[4][2]={{0,0},{0,-1},{0,1},{-1,0}}; 23 int ok(int x,int y){ 24 int xx,yy; 25 int val=a[x][y]; 26 for(int i=0;i<4;i++){ 27 xx=x+dir[i][0]; 28 yy=y+dir[i][1]; 29 if(xx>=0&&xx<=m-1&&yy>=0&&yy<=n-1){ 30 val+=flip[xx][yy]; 31 } 32 } 33 return val&1; 34 } 35 36 int dfs(int k){ 37 int sum,i,j; 38 if(k==m-1){ 39 for(i=0;i<n;i++){ 40 if(ok(k,i)) 41 break; 42 } 43 if(i!=n) 44 return -1; 45 sum=0; 46 for(i=0;i<m;i++){ 47 for(int j=0;j<n;j++) 48 if(flip[i][j]) 49 sum++; 50 } 51 return sum; 52 } 53 for(j=0;j<n;j++){ 54 if(ok(k,j)) 55 flip[k+1][j]=1; 56 } 57 dfs(k+1); 58 } 59 void work(){ 60 int N=1<<n,tem,num; 61 int ret=inf; 62 for(int i=0;i<N;i++){ 63 clc(flip,0); 64 for(int j=n-1,tem=i;j>=0;j--,tem>>=1){ 65 flip[0][j]=tem&1; 66 } 67 num=dfs(0); 68 if(num!=-1&&num<ret){ 69 ret=num; 70 memcpy(p,flip,sizeof(flip)); 71 } 72 } 73 if(ret==inf) 74 printf("IMPOSSIBLE "); 75 else{ 76 for(int i=0;i<m;i++){ 77 for(int j=0;j<n;j++){ 78 if(j==0) 79 printf("%d", p[i][j]); 80 else 81 printf(" %d",p[i][j]); 82 if(j==n-1) 83 printf(" "); 84 } 85 } 86 } 87 } 88 int main(){ 89 //freopen("in.txt","r",stdin); 90 while(~scanf("%d%d",&m,&n)){ 91 for(int i=0;i<m;i++){ 92 for(int j=0;j<n;j++){ 93 scanf("%d",&a[i][j]); 94 } 95 } 96 work(); 97 } 98 return 0; 99 }