ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 百度题

百度题

原创 Linux操作系统 作者:ggggdiu 时间:2008-12-17 15:21:11 0 删除 编辑
百度编程大赛北京总决赛试题!给大家看看!  
  看看难易程度,大家能不能做出来!  
   
  八方块移动游戏要求从一个含8个数字(用1-8表示)的方块以及一个空格方块(用0表示)的3x3矩阵的起始状态开始,不断移动该空格方块以使其和相邻的方块互换,直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动,在四个角落上有2个方向可移动,在其它位置上有3个方向可移动。例如,假设一个3x3矩阵的初始状态为:  
  8   0   3  
  2   1   4  
  7   6   5  
  目标状态为:  
  1   2   3  
  8   0   4  
  7   6   5  
  则一个合法的移动路径为:  
  8   0   3          8   1   3           8   1   3           0   1   3       1   0   3        1   2   3  
  2   1   4   =>   2   0   4   =>   0   2   4   =>   8   2   4   =>8   2   4   =>8   0   4  
  7   6   5          7   6   5           7   6   5           7   6   5       7   6   5         7   6   5  
  另外,在所用可能的从初始状态到目标状态的移动路径中,步数最少的路径被称为最短路径;在上面的例子中,最短路径为5。如果不存在从初始状态到目标状态的任何路径,则称该组状态无解。  
  请设计算法找到从八方块的某初始状态到某目标状态的所有可能路径的最短路径,并用C/C++实现。  
  输入数据:程序需读入已被命名为start.txt的初始状态和已被命名为goal.txt的目标状态,这两个文件都由9个数字组成(0表示空格),1-8表示8个数字方块),每行3个数字,数字之间用空格隔开。假定start.txt和goal.txt不会相同。  
  输出数据:如果输入数据有解,输出一个表示最短路径的非负的整数;如果输入数据无解,输出-1.请在数字输出后在输出一回车换行符。  
  自测用例:如果输入为:start.txt和goal.txt,则产生的输出应为:  
  5  
  如果用  
  7   8   4  
  3   5   6  
  1   0   2  
  替换start.txt中的内容,则产生的输出应为:  
  21  
  如果用  
  7   5   2  
  0   6   3  
  4   1   8  
  替换start.txt中的内容,则产生的输出应为:  
  -1  
  评分规则:我们将首先使用10组不同的start.txt和goal.txt进行测试,每个测试用例的运行时间在一台Intel   Xeon   2.80GHz   4   CPU/6G   内存的Linux机器上应不超过10秒(内存使用不限制),否则该用例不得分;  
  每个选手的得分由两部分组成:正确性得分(10秒内能产生正确结果的测试用例数量x10)和时间性能得分(10秒钟内产生这些正确结果的测试用例的平均运行毫秒数)。正确性得分高的将始终比正确性得分低的排名在前,即使前者的平均运行时间比后者的要长;正确性得分相同的将按平均运行时间的快慢排列。  

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/753964/viewspace-514281/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 一个算法
下一篇: 界面描述引擎
请登录后发表评论 登录
全部评论

注册时间:2008-04-25

  • 博文量
    9
  • 访问量
    6610