首页
社区
课程
招聘
[原创]第二阶段第一题
发表于: 2008-10-17 11:01 2630

[原创]第二阶段第一题

2008-10-17 11:01
2630
先提交程序附件,后面加上说明

total find = 8270
time = 23 sec

一共找到8270种,包括映像
23秒

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

上传的附件:
收藏
免费 0
支持
分享
最新回复 (3)
雪    币: 7325
活跃值: (3803)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
2
total find = 8270
time = 23 sec

上面是 P4 3.0 单线程跑出来的结果,内存2G

简单说明一下上面的程序:

算法是普通的深度优先搜索,回溯算法
数据结构用数组

拼盘是 9*18的,9行,18列
BYTE Puzzle[MAXX][MAXY]={0};

每行有左右界

// 拼盘每行的左右界,大于等于左,小于右符合要求
CHAR BorderX[MAXX] = {0,0,0,0,0,0 ,0 ,  1,  3};
CHAR BorderY[MAXX] = {0,3,5,7,9,11,13, 14, 14};

这样就规定了拼盘的范围,边界用
#define BORDER    ' '

空白(就是可以填滑块)用
#define BLANK    '+'

填进去的就用滑块序号

//每个滑块最多的状态
int bMaxSharp[MAXSHARP]={0};

滑块用一个 12 * 12 * 6的数组表示
work[12][12][6]

这个表示一共有12种滑块,每个滑块最多有12种状态,每个状态有6个数据(就是6个三角形)

6个数据用直角坐标表示,从00 - 36,0x12就表示 x=1,y=2

00 01 02 03 04 05 06
10 11 12 13 14 15 16
20 21 22 23 24 25 26
30 31 32 33 34 35 36

获取数据的xy坐标宏
#define GetSharpX(xy)  ( (CHAR)(((BYTE)(xy))>>4)   )
#define GetSharpY(xy)  ( (CHAR)(((BYTE)(xy))&0x0F) )

规定列y mod 2 = 0的时候,表示是上三角,y mod 2 = 1的时候表示下三角

Puzzle的列y 也是这样规定的,这样的话,滑块的y 和 Puzzle的y 同余,即三角类型匹配

#define CanOverlap(PuzzleY,SharpY)  ((BYTE)((PuzzleY)&1) == (BYTE)((SharpY)&1))?1:0

填入大拼盘Puzzle的时候,xy算法是
    //x = xi-x0+NowX;
    //y = yi-y0+NowY;
x0永远是0,所以可以省略
上传的附件:
2008-10-17 11:24
0
雪    币: 7325
活跃值: (3803)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
3
修复上个版本的小BUG,这下算全了

这次提交虽然修复BUG,但是可能分数还没上次的高

不管了,做完美才最重要

修复的BUG是work数组里面的几个笔误。。。,后面有注释

total find = 11770
time = 36 sec

测试环境:
P4 1.5G  / 768M内存
上传的附件:
2008-10-18 00:50
0
雪    币: 2134
活跃值: (14)
能力值: (RANK:170 )
在线值:
发帖
回帖
粉丝
4
puzzle总数:11770
非重复puzzle数:11770
映像puzzle数:5885
有效puzzle数:5885
结果提交时间 60 小时 50 分钟
结果提交时间长度 = 3650 分钟
结果提交次数 = 2
结果提交为5885,超过5885
得分 = [(5760 - 3650)/5760]^1/10 x 1.0 x 100 - (2 -1 ) x 5 = 85.45
2008-11-12 19:23
0
游客
登录 | 注册 方可回帖
返回
//