首页
社区
课程
招聘
[原创]第二阶段第一题提交
2008-10-18 10:35 2568

[原创]第二阶段第一题提交

2008-10-18 10:35
2568
1:
程序采取递归穷举法, 所有的方块都放置进方格后, 输出一种结果。
2:
模拟人工拼凑法, 从左上扫描到右下, 找到第一个突出点,遍历
找一个能够和突出点紧密结合的方块释放, 然后栈模拟入下一层,
递归自己。
因为存在解法A时, 当找N层突出点一定能有方块M满足条件,
所以当N层凸点找不到任何满足条件的M时, 可退出,
这种“想办法用方块填满“相对“想办法吧方块放下”的穷举方式,
能大大加快速度, 因为只要存在不能放的空格即会立即被找到从而
开始下一次遍历。

数据抽象以及算法实现

参考图片:
图片一是放置好的图, 我们吧图片一左转120°成图片二
然后把右下的脚补齐后, 拉伸成7*16的长方形, 如图三。
其中黑色是拉伸后的填充物, 灰色则是防止判断越界的城墙,
逻辑上都是起哨兵作用。

图三中, 为了简化编程, 讲正向三角形和反向三角形都抽象成
质点, 用方块表示, 但是程序中必须区分是正三角形还是反向,
因为判断图形是否可放置时候需要也仅需要其中一个三角形能对上。
我们对齐在左上建立坐标系后不难发现
Y mod 2 ==0 (反三角)  Y mod 2 ==1 (正三角)

数据结构:
地图有了三角形信息后, 我们抽离出来的图形也需要具有三角属性
这里采用建立透明图片的方法。
观察所有的图片不难发现, 图片限制在3*6的矩形之中,
我们建立一个3*7的矩形, 坐标系同地图坐标系。
将图片搁置其中, 这里如果最靠左边的图形是正三角形时,我们
则空出一列透明列, 否则紧密左对齐,
保证是反三角的方块的Y mod 2 ==0。
所有的用来组合的方块参考数组PosXY的定义
程序中需要判断某个第一接触点(即先竖后横的扫描中第一个空白点)是否能拼凑
方块, 首先让接触点透明图片的第一行的接触点, 透明图片平移, 计算出透明图片
相对于地图的原点, 显然只要原点的y mod 2==0时, 三角形的顺序能一一对应。
这时判断透明图片中的有效点落在地图上的点是否均可搁置, 是则成功, 否则
换另一个形态重试, 如果某一个方块的所有形态都尝试, 则换另一方块, 如果
所有方块都无法搁置, 则需要回溯到上层, 如果回溯到最上层, 则全部解答完

关于镜像:
我们知道地图是能够左右折叠的。 这意味着:
有一种解决方案S, n个方块的取值位 B1..Bn ,
则必然存在一个S’,  n个方块的取值位 B1’..Bn’
所以:
所有数 = 镜像数 * 2       (定理一)
为了我们能够枚举出S的, 但不枚举出S’
我们必须锁选取的数列不构成完全镜像。
假如B1 <> B1’,  则数列 B1, B2|B2’, … Bn| Bn’ 一定不会构成镜像
并且有 count(B1|B1’..Bn|Bn’) == 2 * count(B2|B2’…Bn|Bn’)
结合定理一有, 数列B1, B2|B2’…Bn|Bn’  则为完全镜像数

现在吧方块按照图示归类有
1:完全对成图
2:有3中不同的旋转体, 镜像后是3中
3:有6中不同的旋转体, 但是镜像后依然是6中
4:有3中不同的旋转体, 镜像后有6中
5:有6中不同的旋转体, 镜像后有12中
类别4,5中有3*2=6, 6*2=12, 易知他们所有的旋转体都有不同镜像。
所以只要从这种类别方块中任一个取其中的一个系列互不为镜像值, 其他方块取
全值, 则构成的所有数列不会有完全镜像队列, 于是不会出现镜像图片。
程序中采用的是种类5中的方块6

优化方式:
消耗空间获取效率, 用多个数组O(1)的方式记录当前运行栈。
制作掩码图片的时候,按照错位的方式快速判断三角形方向的正确性
为了减少判断的提速, 增加了城墙概念。
拼凑算法的优化

最终结果:
OS: vista sp1
内存约280k
时间约28秒
非镜像数 5885个

(10/18 today is my birthday, happy birthday jjnet!)

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》,视频+靶场+题目!助力进入CTF世界

上传的附件:
收藏
点赞0
打赏
分享
最新回复 (1)
雪    币: 2134
活跃值: (14)
能力值: (RANK:170 )
在线值:
发帖
回帖
粉丝
Aker 4 2008-10-28 01:35
2
0
sorry for late birthday wish, happy birthday~ jjnet

puzzle总数:5885
非重复puzzle数:5885
映像puzzle数:0
有效puzzle数:5885
结果提交时间 70 小时 35 分钟
结果提交时间长度 = 4235 分钟
结果提交次数 = 1
结果提交为5885,超过5885
得分 = [(5760 - 4235)/5760]^1/10 x 1.0 x 100 - (1 -1 ) x 5 = 87.56
游客
登录 | 注册 方可回帖
返回