翻格子游戏
目录
翻格子游戏
前几天，朋友玩一个解谜类的游戏。中间有一个关卡，大概是这样的：
有一个5*5的板子，初始时，每个格子都是背面朝上。我们可以手动翻转任意一个格子，但其上下左右——如果有的话——的格子也会随之一起翻转，问怎么翻，可以将所有格子都翻到正面朝上。
当时蛮无聊，那就写段代码试试看吧。
这里，手动翻我们定义为主动，而被动当然就很清楚了。
不难想到，对任意一个格子来说，我们主动翻N次和N+2次的结果是一样的。因此，任何一种解决方案都是将每个格子主动翻0或1次。而且，翻格子的先后顺序也是无所谓的。于是，想到一种简单粗暴的办法，穷举呗，一共2^25种情形。
不多说，直接上代码。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int validate(int data, int index, int dimension)
{
int ret;
ret = (data >> index)&0x01;
//left
if(index%dimension > 0)
ret ^= (data >> (index-1))&0x01;
//right
if(index%dimension < dimension-1)
ret ^= (data >> (index+1))&0x01;
//up
if(index/dimension > 0)
ret ^= (data >> (index-dimension))&0x01;
//down
if(index/dimension < dimension-1)
ret ^= (data >> (index+dimension))&0x01;
return ret;
}
int resolve(int data, int d)
{
int ret = 0;
int i;
for (i=0; i<d*d; i++) {
ret = validate(data, i, d);
if (!ret)
return 0;
}
return ret;
}
int main()
{
int map=0;
int ret = -1;
int d = 5;
for (map=0; map<pow(2,d*d); map++) {
ret = resolve(map, d);
if (ret) {
printf("%x\n", map);
}
}
return 0;
}解决方案采用25个bit来描述，每个bit，1表示主动翻，0表示不主动翻。采用位操作不仅节省了空间，而且提高了效率。
结果发现，解决方案不止一种。
当然，需要注意的是，如果6*6的格子，用32bit整型会导致溢出。