FliptilePOJ3279二进制压缩枚举解题报告

做这题之前，我们首先需要理解一个现象：除了最后一行，其他任何一行上的1都可以通过下一行的翻转转换成0。

也就是说，除了最后一行外，我们总是可以通过翻转，将前n-1行翻成全0。

只要按照这样的原则：对于某一个位置x，如果它的上一个是1，就翻转它，如果是0，就不翻转。

知道了这个，我们应该就能想到，第一行的翻法直接就决定了后面的所有的翻法，这就是我们解决这道题目的思路，即枚举第一行所有可能的翻法，这里，如果用循来枚举，未免太浪费时间了，所以，这里采取了一种二进制压缩的方法。

首先让我们来学习一下左移<<的概念，其实很好理解，就是将一个数转换为二进制，然后向左移动若干位，然后在多出来的位置上补零，比如，对于5<<2,5的二进制为101，左移两位就是10100，那么最后的结果就是20,。

利用这个特点，我们可以通过使用一个特殊的数字1，来解决这个枚举问题。枚举的第一步就是确定到底要改变哪几位数，联想到二进制，我们可以这样处理，就题目的测试数据而言，一行有四个数，用一个二进制数xxxx表示，易知，xxxx一共有2^4种排列，其实也是1<<4，之所以这样写，是因为这比pow要快，所以，我们让k从0开始枚举到15，也就是0000到1111，然后规定，只要是带1的位置，就要翻转这个位置的数字，问题又来了，怎么知道哪一位是1,呢，这里还是用到了二进制，即与运算，我们让k分别与1000,0100,0010,0001进行与运算，分别对应不同的位，如果结果不是1，说明这一位上不是0，是不是灰常巧妙，当然，那四个值依然是通过1的左移来计算出来的，核心的东西讲完了，下面看看代码吧

#include
#include
#include
using namespace std;
const int N = 16;
int g[N][N], t[N][N], f[N][N];
int cnt, n, m;
int x[4] = {0, 0, -1, 1};
int y[4] = { -1, 1, 0, 0};
void flip(int i, int j)//翻转
{
++cnt, f[i][j] = 1;//步数加1，记录翻转了哪个瓷砖
t[i][j] = !t[i][j];//首先翻转自己
for(int k = 0; k <4; ++k)//向四个方向寻找，找到就翻转，这里使用了异或
if(i + x[k] > -1 && j + y[k] > -1)
t[i + x[k]][j + y[k]] ^= 1;
}
bool ok(int k)//对于第一行的每一种情况，判断是否能够产生最终的结果
{
cnt = 0;//初始化步数
memcpy(t, g, sizeof(t));//初始化临时数组，作为原始数组的副本
for(int j = 0; j if(k & (1 <<(m - 1 - j)))//对于k的每一个取值，如1010，找到不为0的列，因为只需要翻转1就可以了，用到了与运算
flip(0, j);//如果某一列不为0，就翻转第一行的这个位置
for(int i = 1; i for(int j = 0; j if(t[i - 1][j]) flip(i, j);//如果该列上一个位置是1，那么这个位置需要翻，否则不需要翻
for(int j = 0; j if(t[n - 1][j]) return false;
return true;
}
int main()
{
int ans, p;
while(~scanf("%d%d", &n, &m))
{
for(int i = 0; i for(int j = 0; j scanf("%d", &g[i][j]);
ans = n * m + 1, p = -1;//初始化
for(int i = 0; i <(1 < if(ok(i) && cnt ans = cnt, p = i;
memset(f, 0, sizeof(f));
if(p >= 0)//最后找到的就是最少的翻法，模拟一遍，然后输出
{
ok(p);
for(int i = 0; i for(int j = 0; j printf("%d%c", f[i][j], j }
else puts("IMPOSSIBLE");
}
return 0;
}