首先构造两个数组,一个是容器,一个是各个板块
每个板块又包含了1-12种变化(6种旋转及翻转),为了优化代码,板块信息全部都用静态数组
这个板块数组的定义如下
typedef struct _PEDIY_BLOCK {
BYTE used;
BYTE number_of_variant;
BYTE index;
BYTE data[12][4][6];
}PEDIY_BLOCK;
第一个参数used用于循环中避免重复取用
第二个参数number_of_variant表示该板块有几种变化
第三个参数index原来是考虑用来保存第一种变化被应用到,但在实际实现中这个值没用上
第四个参数data数组保存了该板块的所有变化信息
如果某个字节最高位为1,表示该位置为空,没有数据
如果最高位不为0,最低位为0时表示向上的三角形,为1时表示向下的三角形
另外第4和第5位用于表示行数
例如:
// AVA
// VAV
0x00, 0x01, 0x00, 0x80, 0x80, 0x80,
0x11, 0x10, 0x11, 0x80, 0x80, 0x80,
0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
注释中A表示向上的三角形,V表示向下的三角形
另外,采用4*6的数组是因为最大高度和宽度分别为4和6,虽然内存使用上有不少浪费但考虑到速度还是将就一下了
容器数组采用宽18高11,这是因为该钻石容器的实际长宽分别为13和8,考虑到后面计算方便并且避免溢出,所以采用容量13+6-1和8+4-1
该数组也预先初始化好,0xFF表示无效空间,0x00表示向上的三角形,0x01表示向下的三角形
好了,准备工作到这里就可以了
接下来的算法很简单,我们从容器的上方开始遍历空着的有效区域,从上到下,从左到右
一旦发现空格子,从板块数组中任意取一块出来测试,先根据容器中该格子需要的三角形过滤到不合格的板块
这里主要是判断该板块所对应在容器中的位置是否全部有效或是是否已经被占用,如果合格则填入容器,并递归查找下去。
如果12块板块都用成功填入,则输出一个结果,并且继续当前的计算。
当容器中所有和该取出的板块相对应的位置
我用IBM T60P 2GB内存2.16GHz的CPU计算时如果不开屏幕输出大约需要不到3分钟,开屏幕输出会略慢一些