首页
社区
课程
招聘
[原创][第二阶段◇第一题答案]看雪论坛.腾讯公司2008软件安全竞赛
发表于: 2008-10-16 11:55 2961

[原创][第二阶段◇第一题答案]看雪论坛.腾讯公司2008软件安全竞赛

2008-10-16 11:55
2961
先上传个附件

start time: 04:47"36
end time: 04:50"12
number of solution found: 3402

用/silent参数可以关闭屏幕输出,不用的话会慢一些
计算结果里面包含了对称的,因此应该是3402/2 = 1701

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

上传的附件:
收藏
免费 0
支持
分享
最新回复 (6)
雪    币: 503
活跃值: (80)
能力值: (RANK:280 )
在线值:
发帖
回帖
粉丝
2
因为想尽可能优化代码速度,所以旋转和翻转都用静态数组实现的
另外输出文件是pediy_2_1.log
2008-10-16 11:57
0
雪    币: 503
活跃值: (80)
能力值: (RANK:280 )
在线值:
发帖
回帖
粉丝
3
首先构造两个数组,一个是容器,一个是各个板块
每个板块又包含了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分钟,开屏幕输出会略慢一些
2008-10-16 12:25
0
雪    币: 503
活跃值: (80)
能力值: (RANK:280 )
在线值:
发帖
回帖
粉丝
4
代码写的有些乱,之前想用的一些变量和结构后来又没用到还请见谅
2008-10-16 12:28
0
雪    币: 503
活跃值: (80)
能力值: (RANK:280 )
在线值:
发帖
回帖
粉丝
5
输出的时候是按照下图编码的,当然使用到的任意块都有可能是旋转或是翻转后的

上传的附件:
2008-10-16 16:37
0
雪    币: 503
活跃值: (80)
能力值: (RANK:280 )
在线值:
发帖
回帖
粉丝
6
这一题实在太无语了,为什么文档中的图片顺序不一致。。。

只好重新提交一次,希望不要因此扣分


start time: 10:24"36
end time: 10:26"20
number of solution found: 3402
上传的附件:
2008-10-16 17:32
0
雪    币: 2134
活跃值: (14)
能力值: (RANK:170 )
在线值:
发帖
回帖
粉丝
7
puzzle总数:3402
非重复puzzle数:3402
映像puzzle数:444
有效puzzle数:2958
结果提交时间 29 小时 31 分钟
结果提交时间长度 = 1771 分钟
结果提交次数 = 2
结果提交为1000-5885
得分 = [(5760 - 1771)/5760]^1/10 x 0.9 x 100 - (2 -1 ) x 5 = 81.75

呵呵,两次提交,差了5分多
2008-11-12 18:24
0
游客
登录 | 注册 方可回帖
返回
//