ACM国际大学生程序设计竞赛中的推箱子
ACM国际大学生程序设计竞赛(ACM-ICPC)第一届于1977年举行。到2010年一共办了34届(第34届总决赛在中国哈尔滨举行的)。
ACM-Association for Computing Machinery , 美国计算机协会.
ICPC-International Collegiate Programming Contest , 国际大学生程序设计竞赛.
推箱子似乎也屡次被这个比赛用作练习题或者地区性选拔赛的题目。
如：
（一）给出一个只有一个箱子的关卡，求最少推动步数
(North America - Northeast - 2006/2007)
http://acm.uva.es/archive/nuevoportal/data/problem.php?p=3745
http://acm.hdu.edu.cn/showproblem.php?pid=1254
（二）Harder Sokoban Problem
给定关卡迷宫，以及一个目标位置，求如何放置箱子和人的初始位置，使得移动步数最大？
(Northeastern Europe 2004 Far-Eastern Subregion)
http://acm.tju.edu.cn/acm/showp2370.html 只会第一题，动态规划就行了
第二题应该也差不多吧...应该也是动态规划....
回复 2# 的帖子
不行的，推箱子已经被证明是NP难问题了，动态规划不可能成功，只能搜索。不过这题状态数相当少（只考虑人和箱子相邻的状态就够了），直接搜就可以了，时间复杂度O(mn)，不会超时。第2题类似于第一题，把每一种情况的步数算出来即可，用记忆化的方法可以使时间复杂度降到O(mn)，一样不超时。
回复 2# 的帖子
2楼是中山的？那里信息学好强好强啊……广州的表示无限膜拜…… 只会切水的菜鸟路过。。
页:
[1]