ACM国际大学生程序设计竞赛中的推箱子

sokoban

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

oyh

只会第一题，动态规划就行了
第二题应该也差不多吧...应该也是动态规划....

clw960130

不行的，推箱子已经被证明是NP难问题了，动态规划不可能成功，只能搜索。不过这题状态数相当少（只考虑人和箱子相邻的状态就够了），直接搜就可以了，时间复杂度O(mn)，不会超时。
第2题类似于第一题，把每一种情况的步数算出来即可，用记忆化的方法可以使时间复杂度降到O(mn)，一样不超时。

clw960130

2楼是中山的？那里信息学好强好强啊……广州的表示无限膜拜……

Uriel

只会切水的菜鸟路过。。