迷宫夺宝.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,迷宫夺宝,Designed by,JinZhao,,cs,.,ustc,.,edu,.,cn,/cs0211,比赛题目,给定,27*,27,的正方形迷宫，迷宫中间随机产生正分（,1-50,绿色圆点）和负分（,-50-1,黑色圆点）；比赛 时，在规定时间内比较比赛双方的 总得分,比赛规则（初稿）,1.,分组比赛，小组组数及参赛队数根据最后参赛选手数量抽签确定；,2.,每组采取单循环比赛，积分前两名出线；若积分相同则比较总净胜分数；,3.,每场比赛时间两分钟，时间结束时比较双方得分总数；,4.,胜,3,分；平,2,分；负,1,分；,5.,比赛时，参赛队将算法上交裁判，由裁判执行程序,6.,严禁违规操作（每场比赛后裁判将查看胜方源码，若发现违规现象，则取消后面比赛资格，对方胜）,此规则：组委会保留最终修改、解释权。,本活动相关信息请见,班级主页,-,常用链接,-,迷宫寻宝,Feedback:,yuxinustc.edu,Maze Mouse,迷宫构造,迷宫由二维,0-1,矩阵构成，（,i,j,）,处值为,1,表示该位置有障碍不能通过。,（,1,，,1,）表示入口，（,7,，,6,）表示出口。,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,最短路径,算法分两步进行，第一步标记可到达的网格位置，直到到达宝藏位置，第二步逆向构造从宝藏到出发点的最短路径。,开始时把出发点位置赋为,2,。,1,1,1,1,1,1,1,1,1,1,5,4,1,0,0,0,0,1,1,4,3,1,1,1,0,0,1,1,3,A,3,4,1,0,0,1,1,4,3,4,1,1,B,0,1,1,1,4,5,6,1,10,0,1,1,1,1,1,7,8,9,10,1,1,1,1,1,8,9,10,0,1,1,1,1,1,1,1,1,1,1,圣诞快乐,考试别挂,