3320 - 翻转棋
农夫约翰知道，聪明的奶牛可以产更多的牛奶。他为奶牛设计了一种智力游戏，名叫翻转棋。翻转棋可以分成M × N (1 ≤ M, N ≤ 15)个格子，每个格子有两种颜色，一面是黑的，一面是白的。
一旦翻转某个格子，这个格子的颜色就会颠倒。如果把所有的格子都翻成白的，就算奶牛赢了。然而，奶牛的蹄子很大，一旦它们打算翻转某个格子，这个格子附近（即和这个格子有公共边）的格子也会被翻转。一直翻来翻去也很无聊，奶牛们想最小化必须翻动的次数。
请帮助奶牛确定翻动的最少次数和具体的翻法。如果最小解有多个，则输出在字典序意义下最小的那个，如果不可能完成任务，则只要输出一行单词：IMPOSSIBLE。
Input
第一行：两个用空格分开的整数：M和N
第二行到M + 1行：第i + 1行从左至右依次描述了棋盘第i行的的颜色，共记N个用空格分开的整数，1 代表黑色，0 代表白色。
Output
第一行到第M行：每行输出N个用空格分开的整数，表示在这个格子上翻转的次数。
Examples
Input
4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
Output
0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0
Hint
（另外还有一个解是
0 1 1 0
0 0 0 0
0 0 0 00 1 1 0 但是这个解在字典序意义下没有样例来得<br />小）
Solution C++
/* Name: fliptile Author: 靳帅祥 Date: 22/10/14 08:58 Description: */ #include <cstdio> #include <climits> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <cstdlib> using namespace std; int dx[4]={0,1,-1, 0}; int dy[4]={1,0, 0,-1}; int H=0,L=0; bool jsx=false; class node{ public: int Step; int G[20][20]; bool operator < (const node& b) const { if(Step==b.Step){ for(int i=1;i<=H;++i){ for(int j=1;j<=L;++j){ if(G[i][j] < b.G[i][j]) return true; else return false; } } return true; } return Step < b.Step; } }E,Map,Ans; inline bool PD(int x,int y){ if(x>0 && y>0 && x<=H && y<=L) return true; return false; } inline bool Full(node b){ for(int i=1;i<=H;++i){ for(int j=1;j<=L;++j){ if(b.G[i][j]!=0) return false; } } return true; } inline void Turn(int x,int y){ Map.G[x][y]++; Map.Step++; E.G[x][y]=!E.G[x][y]; for(int i=0;i<4;++i){ int xx=x+dx[i],yy=y+dy[i]; if(PD(xx,yy)) E.G[xx][yy]=!E.G[xx][yy]; } } inline void DEAL(){ node temp1=E; node temp2=Map;//储存状态 for(int i=2;i<=H;++i){ for(int j=1;j<=L;++j){ if(E.G[i-1][j]==1) Turn(i,j); } } if(Full(E)){ if(!jsx){ Ans=Map; jsx=true; } else{ if(Map < Ans){ Ans=Map; } } } E=temp1; Map=temp2;//还原 } void DFS(int pos,int F){ if(pos==L+1){ DEAL(); return; } if(F==0){ DFS(pos+1,0); DFS(pos+1,1); } else{ node t1=E,t2=Map; Turn(1,pos); DFS(pos+1,0); DFS(pos+1,1); E=t1; Map=t2;//还原 } } int main(){ //freopen("fliptile.in","r",stdin); //freopen("fliptile.out","w",stdout); scanf("%d%d",&H,&L); for(int i=1;i<=H;++i){ for(int j=1;j<=L;++j){ scanf("%d",&E.G[i][j]); } } //1.第一行不翻转 //2.枚举第一行的状态 2^15..... DFS(1,0); DFS(1,1); if(jsx==true){ for(int i=1;i<=H;++i){ printf("%d",Ans.G[i][1]); for(int j=2;j<=L;++j){ printf(" %d",Ans.G[i][j]); } printf("\n"); } } else{ printf("IMPOSSIBLE\n"); } fclose(stdin); fclose(stdout); return 0; }
Hint
（另外还有一个解是
0 1 1 0
0 0 0 0
0 0 0 0
0 1 1 0
但是这个解在字典序意义下没有样例来得<br />
小）