题目：
Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M × N grid (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) of square tiles, each of which is colored black on one side and white on the other side.
As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.
Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word "IMPOSSIBLE".
Input
Output
Sample Input
4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
Sample Output
0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0
这道题放在kuangbin带你飞的第一个专题的第4题可谓是萌新劝退题，难度不小。
主要涉及的方法有局部枚举和状态压缩
首先先明确一个细节：所有的地板翻动次数只能是0次或1次，因为每翻动两次，地板的状态不变，所以如果翻动次数为2或3，则跟翻动0次和1次的状态是一样的，所以次数只能是0或1.
局部枚举法的概念看这里：https://blog.csdn.net/TZR986981442/article/details/104425015
这里因为第一行的翻动情况决定了所有地板的翻动情况，所以只用枚举第一行的所有情况即可。
状态压缩的概念看这里：https://blog.csdn.net/weixin_33966095/article/details/94504276
这里因为第一行的翻动情况的数量为2^N(因为每个木板都有翻动0次或1次两个选择），所以这里顺理成章的用一个二进制数来记录一种翻动情况。
首先是几个变量的意义：
1 int M=0,N=0; //地面的长和宽 2 int tiles[15][15]={0}; //记录初始时的地板状态 3 int simu_tiles[15][15]={0}; //记录模拟过程中的地板翻动状态（值表示翻动次数—） 4 int best_tiles[15][15]={0}; //记录最佳模板翻动状态
这里还有一个隐藏的问题，就是如何知道某块地板当前的状态，（不去动手写代码很容易忽略这个问题），需要通过检查这块地板以及周围地板的翻动次数，结合这块地板初始时的状态才能确定现在的状态。
1 //获取某块地板的状态 2 int get_tile_status(int x,int y){ 3 int num=tiles[x][y]; //初始状态 4 int X[4]={0,0,-1,1}; 5 int Y[4]={1,-1,0,0}; 6 num+=simu_tiles[x][y]; //先加上自己的翻动次数 7 for(int i=0;i<4;i++){ 8 int _x=x+X[i],_y=y+Y[i]; 9 if(_x>=0&&_x<M&&_y>=0&&_y<N){ 10 num+=simu_tiles[_x][_y]; //加上周围地板翻动导致的本地版翻动 11 } 12 } 13 return num%2; //取模2的余数即为该地板的状态 14 }
然后是对第一行的每种情况进行的模拟翻地板过程
1 //从第二行开始模拟，计算所需的翻动次数 2 int simulate(){ 3 for(int i=1;i<M;i++){ 4 for(int j=0;j<N;j++){ 5 if(get_tile_status(i-1, j)!=0){ 6 simu_tiles[i][j]=1; 7 } 8 } 9 } 10 //通过检查最后一行是否全部为0来判断是否存在解决方案 11 for(int i=0;i<N;i++){ 12 if(get_tile_status(M-1,i)!=0){ 13 return -1; 14 } 15 } 16 //计算翻转次数 17 int num=0; 18 for(int i=0;i<M;i++){ 19 for(int j=0;j<N;j++){ 20 num+=simu_tiles[i][j]; 21 } 22 } 23 return num; 24 }
关于本题最难的一部分，即状态压缩和局部枚举的实现：
1 int best_num=-1; //最小翻动次数 2 //状态压缩：按照字典序列举第一行的所有可能性：2^N种 3 for(int i=0;i<(1<<N);i++){//这里i按照字典序逐渐增大 4 //每次模拟前清空simu_tiles 5 memset(simu_tiles,0,sizeof(simu_tiles)); 6 //将第一行的地板状态存入simu_tiles 7 for(int j=0;j<N;j++){ 8 simu_tiles[0][N-j-1]=(i>>j)&1; 9 } 10 //模拟，获取翻动次数 11 int num=simulate(); 12 if(num>0&&(best_num<0||num<best_num)){ 13 best_num=num; 14 //记录最佳翻动状态 15 memcpy(best_tiles,simu_tiles,sizeof(simu_tiles)); 16 } 17 }
其中，1<<N就是2^N，(i>>j)&1就是i这个数的二进制形态从右往左的第j位上的值
总的AC代码：
1 #include<iostream> 2 #include<string.h> 3 using namespace std; 4 5 int M=0,N=0; //地面的长和宽 6 int tiles[15][15]={0}; //记录初始时的地板状态 7 int simu_tiles[15][15]={0}; //记录模拟过程中的地板翻动状态（值表示翻动次数—） 8 int best_tiles[15][15]={0}; //记录最佳模板翻动状态 9 10 //获取某块地板的状态 11 int get_tile_status(int x,int y){ 12 int num=tiles[x][y]; //初始状态 13 int X[4]={0,0,-1,1}; 14 int Y[4]={1,-1,0,0}; 15 num+=simu_tiles[x][y]; //先加上自己的翻动次数 16 for(int i=0;i<4;i++){ 17 int _x=x+X[i],_y=y+Y[i]; 18 if(_x>=0&&_x<M&&_y>=0&&_y<N){ 19 num+=simu_tiles[_x][_y]; //加上周围地板翻动导致的本地版翻动 20 } 21 } 22 return num%2; //取模2的余数即为该地板的状态 23 } 24 25 //从第二行开始模拟，计算所需的翻动次数 26 int simulate(){ 27 for(int i=1;i<M;i++){ 28 for(int j=0;j<N;j++){ 29 if(get_tile_status(i-1, j)!=0){ 30 simu_tiles[i][j]=1; 31 } 32 } 33 } 34 //通过检查最后一行是否全部为0来判断是否存在解决方案 35 for(int i=0;i<N;i++){ 36 if(get_tile_status(M-1,i)!=0){ 37 return -1; 38 } 39 } 40 //计算翻转次数 41 int num=0; 42 for(int i=0;i<M;i++){ 43 for(int j=0;j<N;j++){ 44 num+=simu_tiles[i][j]; 45 } 46 } 47 return num; 48 } 49 50 int main(){ 51 cin >>M>>N; 52 //读取初始地板信息 53 for(int i=0;i<M;i++){ 54 for(int j=0;j<N;j++){ 55 cin >>tiles[i][j]; 56 } 57 } 58 int best_num=-1; //最小翻动次数 59 //状态压缩：按照字典序列举第一行的所有可能性：2^N种 60 for(int i=0;i<(1<<N);i++){//这里i按照字典序逐渐增大 61 //每次模拟前清空simu_tiles 62 memset(simu_tiles,0,sizeof(simu_tiles)); 63 //将第一行的地板状态存入simu_tiles 64 for(int j=0;j<N;j++){ 65 simu_tiles[0][N-j-1]=(i>>j)&1; 66 } 67 //模拟，获取翻动次数 68 int num=simulate(); 69 if(num>0&&(best_num<0||num<best_num)){ 70 best_num=num; 71 //记录最佳翻动状态 72 memcpy(best_tiles,simu_tiles,sizeof(simu_tiles)); 73 } 74 } 75 76 if(best_num<0){ 77 //无解 78 cout <<"IMPOSSIBLE"<<endl; 79 }else{ 80 for(int i=0;i<M;i++){ 81 for(int j=0;j<N;j++){ 82 cout <<best_tiles[i][j]<<" "; 83 } 84 cout <<endl; 85 } 86 } 87 88 system("pause"); 89 return 0; 90 }
原文：https://www.cnblogs.com/shiyu-coder/p/13132519.html
