POJ_1753
时隔多日，已经是第3次写这个题目了，在熟悉了位运算之后使得更有效率地解决了这个问题。
同时，这个题目在枚举上也有一点小的技巧。如果要是暴力枚举的话，一旦棋盘到了16*16的话显然就吃不消了（一个东欧区域赛的题目），实际上我们完全可以只枚举第一行的操作，之后，如果我们想把棋子全部翻成一种颜色的话，那么第二行的操作就是固定的了（因为第一行的棋子的状态对第二行棋子的翻转进行了约束，如果想把第一行的棋子变成白色，那么第二行中位于第一行黑色棋子下方的位置必须翻转，反之亦然），那么第三行、第四行的操作显然也是固定的了。
这样即使是16*16的棋盘也只有15*16*2^16的复杂度，是可以接受的。
#include<stdio.h>
#include<string.h>
int fresh, steps, dx[] = {0, -1, 1, 0, 0}, dy[] = {0, 0, 0, -1, 1};
void init()
{
char ch;
fresh = 0;
for(int i = 0; i < 4; i ++)
{
for(int j = 0; j < 4; j ++)
fresh = (fresh << 1) + ((ch = getchar()) == 'b' ? 1 : 0);
getchar();
}
}
void flip(int x, int y, int &st)
{
if(x >= 0 && x < 4 && y >= 0 && y < 4)
st ^= 1 << (x * 4 + y);
}
void dfs(int cur, int num, int st, int flag)
{
if(cur == 4)
{
if(st == 0xffff || st == 0)
steps = num < steps ? num : steps;
return;
}
int x, y;
for(int i = cur - 1, j = 0; j < 4; ++ j)
if(((st & (1 << (i * 4 + j))) >> (i * 4 + j)) ^ flag )
{
for(int k = 0; k < 5; ++ k)
{
x = cur + dx[k];
y = j + dy[k];
flip(x, y, st);
}
++ num;
}
dfs(cur + 1, num, st, flag);
}
int solve()
{
steps = 0x7fffffff;
for(int i = 0; i < 16; ++ i)
{
int num = 0, st = fresh, x, y;
for(int j = 0; j < 4; ++ j)
{
if(i & (1 << j))
{
for(int k = 0; k < 5; k ++)
{
x = 0 + dx[k];
y = j + dy[k];
flip(x, y, st);
}
num ++;
}
}
dfs(1, num, st, 0);
dfs(1, num, st, 1);
}
return steps == 0x7fffffff ? -1 : steps;
}
int main()
{
init();
if(solve() != -1)
printf("%d\n", steps);
else
printf("Impossible\n");
return 0;
}