九度OJ 9月赛第二场 题目1542：黑白迷阵 （状态压缩DP）

题目描述：

黑白迷阵是一个GrassLand编写的手机游戏，它的规则非常简单，有如下4*5的棋盘，其中一些是格子是黑色，一些格子是白色的，每当点击其中某一个格子，它以及它上下左右五个格子的颜色会发出反转，如下图

游戏胜利的条件很简单，把所有的格子变为黑色即可。
GrassLand想知道，给定一个游戏格局，至少需要几次点击，就可以获得游戏的胜利。

输入：

输入包含多组测试用例。输入的第一行为一个整数T，代表共有的测试用例数。紧接着为T组测试用例。
每组测试用例，为由四行五列01阵列表示的游戏格局，其中0代表该格子的颜色为白色，1代表该格子的颜色为黑色。

输出：

对于每组测试用例，输出为一个整数，为至少需要的点击次数。数据保证所给格局可以在有限步内取得胜利。

样例输入：

20011101111111111111100111011111111011100

样例输出：

12

思路：先确定第一行的翻转方式，枚举出所有的状态，采用二进制编码，最后再判断最后一行是否全黑，如果不是则无解，如果是，则记录

最小的翻转次数并更新。

代码：

#include<iostream>#include<cstring>using namespace std;const int dx[5]={-1,0,0,0,1};const int dy[5]={0,-1,0,1,0};const int MAX_M=6;const int MAX_N=6;int M=4,N=5;bool tile[MAX_M][MAX_N];int flip[MAX_M][MAX_N];//查询坐标(x,y)处的颜色 int getstate(int x,int y){int c=tile[x][y];for(int d=0; d<5; d++){int x2=x+dx[d],y2=y+dy[d];if(0 <= x2 && x2<M && 0<= y2 && y2<N){c += flip[x2][y2];}}return c % 2;}int cal(){for(int i=1; i<M; i++) //从第二行开始求出翻转的方法 {for(int j=0; j<N; j++){if(getstate(i-1,j) != 0) //这个格子是白色，必须翻转 {flip[i][j]=1;}} }//判断最后一行是否全黑 for(int j=0; j<N; j++){if(getstate(M-1,j) != 0){return -1;}}//统计翻转次数 int res=0;for(int i=0; i<M; i++){for(int j=0; j<N; j++){res += flip[i][j];}}return res;}void solve(){int res=-1;for(int i=0; i< 1<<N; i++){memset(flip,0,sizeof(flip));for(int j=0; j<N; j++){flip[0][N-j-1]= (i>>j)&1; //枚举第一行的所有状态 }int num=cal();if(num >=0 && (res<0 || res >num)){res=num;}}cout<<res<<endl;} int main(){int T;cin>>T;while(T--){for(int i=0;i<M;i++){for(int j=0;j<N;j++){char tmp;cin>>tmp;tmp -='0';tmp = !tmp;tile[i][j]=tmp;}}solve();}return 0;}