yq_118 发表于 2009-6-8 20:14:36 2#
没研究过这个，应该可能有多项式时间算法吧
————————————————————
sokoban 发表于2009-6-8 20:16:28
回复 2# 的帖子
推箱子是 PSPACE 完全问题，基本不可能有多项式时间算法。
————————————————————
anian 发表于 2009-6-8 23:46:58
可能是exp关卡设计不是很完善的缘故， 这个关卡的答案不一定如sokoban兄说的那样走。
Solution(pushes 86, moves 795, in-lines 72, changes 55, steps 72):
uuulllllllllddddddDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuullllllllddddddDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrurrUUUUUUlLdlluRdllluRuulllllllldddddDDrddlUUdlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrrrrrrrrrrrrrrruuuuuuuuuuuuuullllddddddDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuullllllllDDDDDDDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrruuuuuuuuuuuuuullllddddddDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuullllllllddlLdlluRdllluRuullllllllddlLdlluRdllluRuullllllddrddlUU
Solution(pushes 106, moves 743, in-lines 70, changes 55, steps 70):
uuulllllllllddddddDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrurrUUUUUUlLdlluRdllluRuullllllllddddddDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrurrUUUUUUlLdlluRdllluRuulllllllldddddDDrddlUUdlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrrrrrrrrrrrrrrruuuuuuuuuuuuuullllDDDDDDDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrurrUUUUUUlLdlluRdllluRuullllllllDDDDDDDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrruuuuuuuuuuuuuullllDDDDDDDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuullllllllddlLdlluRdllluRuullllllllddlLdlluRdllluRuullllllddrddlUU
[ 本帖最后由 anian 于 2009-6-9 01:15 编辑 ]
————————————————————
anian 发表于 2009-6-8 23:55:00
如果将关卡改变一点就没有问题了:
########
#--##########
#--##########
#--############
#-------
#--#---------
#--#---------
#--#----------#
#.####
#-###
#-######
#-###
#-######
#-###
#-##
#-###
#-##--#-#--*-*--##---#--*-*--##---#--*-*--#
#--#-
#--##$-
#-#-----
#--#---#-----
#--#---#-----
#--#--
#-#-@#
#--#-####
#-##-#---####
#-##-#---####
#-##-
#--#-
#--####
#-#---#-
#--#---#---#-
#--#---#---#-
#--#--
#-####
-----
#-#*--
#-##---
#-#*--
#-##---
#-#*--
#-##--#-----
-----#---###*-#---#---###*-#---#---###*-
#--#-----
-----#--*#----#---#--*#----#---#--*#----
#--#-----
-----
#-#---
#--#---
#-#---
#--#---
#-#---
#--#--#-----
-----#---
#-####
#--#---
#-####
#--#---
#-####
#-#-----
-----####
#-#---
#--####
#-#---
#--####
#-#---
#-#-----
---------#--*--#------#--*--#------#--*--
#-#-----
############
#-###########
#-###########
#-##-######
#-----------------------------------------------#
#################################################
[ 本帖最后由 anian 于 2009-6-9 00:00 编辑 ]
t.png
