题目链接：http://poj.org/problem?id=3279
题目大意：有一个n*m的格子，每个格子都有黑白两面（0表示白色，1表示黑色）。我们需要把所有的格子都反转成黑色，每反转一个格子，它上下左右的格子都会跟着反转。请求出用最小步数完成反转时每个格子反转的次数。有多个解时，输出字典序最小的一组。
解题思路：只要枚举第一行的2^m种情况，如果一个位置上一行是1，那这个位置一定要反转，因为只有这一行能改变上一行，所以每一行的状态都是由前一行决定的。只要最后判断最后一行是不是都是0即可，关于最小字典序，只要从右往左枚举，第一个方案就是正解。（时间复杂度O（n*m*2^m）。
代码：
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 const int N=20; 5 6 int n,m; 7 bool flag; 8 int map[N][N],sta[N][N],tmp[N][N];//sta表示踩或不踩 9 int d[5][2]={{0,1},{1,0},{0,0},{0,-1},{-1,0}}; 10 11 12 //反转坐标为(i，j)的格子 13 void reverse(int i,int j,int s[][N]){ 14 for(int k=0;k<5;k++){ 15 int x=i+d[k][0]; 16 int y=j+d[k][1]; 17 s[x][y]=!s[x][y]; 18 } 19 } 20 21 void dfs(int y){ 22 if(flag) 23 return; 24 if(y>=1){ 25 //不踩 26 sta[1][y]=0; 27 dfs(y-1); 28 //踩 29 sta[1][y]=1; 30 reverse(1,y,map); 31 dfs(y-1); 32 reverse(1,y,map); 33 } 34 else{ 35 for(int i=1;i<=n;i++){ 36 for(int j=1;j<=m;j++){ 37 tmp[i][j]=map[i][j]; 38 } 39 } 40 for(int i=2;i<=n;i++){ 41 for(int j=1;j<=m;j++){ 42 sta[i][j]=0; 43 if(tmp[i-1][j]==1){ 44 reverse(i,j,tmp); 45 sta[i][j]=1; 46 } 47 } 48 } 49 50 bool sign=true; 51 for(int i=1;i<=m;i++){ 52 if(tmp[n][i]==1){ 53 sign=false; 54 break; 55 } 56 } 57 if(sign){ 58 flag=true; 59 for(int i=1;i<=n;i++){ 60 for(int j=1;j<=m;j++){ 61 if(j==m) 62 printf("%d\n",sta[i][j]); 63 else 64 printf("%d ",sta[i][j]); 65 } 66 } 67 } 68 } 69 } 70 71 int main(){ 72 while(~scanf("%d%d",&n,&m)){ 73 memset(sta,0,sizeof(sta)); 74 flag=false; 75 for(int i=1;i<=n;i++){ 76 for(int j=1;j<=m;j++){ 77 scanf("%d",&map[i][j]); 78 } 79 } 80 dfs(m); 81 if(!flag) 82 puts("IMPOSSIBLE"); 83 } 84 return 0; 85 }
原文：http://www.cnblogs.com/fu3638/p/7512656.html