多谢ChangKai 兄答疑。ChangKai 兄贴的似乎和 jinyou 兄的是一样的。这一关的图如26楼所示。“人”的左边是墙,但是解法的第一步是 l,我百思不得其解。
粗心所致,导出的原关卡与jinyou兄的弄混,对不起sokoban兄了。
同样是李金玉的这一关,答案大约要10W。
################################
# # # # # # # # # # #
# #.$ #.$ #.$ #.$ #.$ #
#.$# #.$# #.$# #.$# #.$# #
# #.$# #.$# #.$# #.$# #.$##
#.$# #.$# #.$# #.$# #.$# #
# #.$# #.$# #.$# #.$# #.$#
#.$# #.$# #.$# #.$# #.$# #
# #.$# #.$# #.$# #.$# #.$#
#.$# #.$# #.$# #.$# #.$# #
# #.$# #.$# #.$# #.$# #.$#
#.$# #.$# #.$# #.$# #.$# #
# #.$# #.$# #.$# #.$# #.$#
#.$# #.$# #.$# #.$# #.$# #
# #.$# #.$# #.$# #.$# #.$#
#.$# #.$# #.$# #.$# #.$# #
# #.$# #.$# #.$# #.$# #.$#
#.$# #.$# #.$# #.$# #.$# #
# #.$# #.$# #.$# #.$# #.$#
#.$# #.$# #.$# #.$# #.$# #
# #.$# #.$# #.$# #.$# #.$#
#.$ #.$ #.$ #.$ #.$ #
# @# # # # # # # # # #
###############################
Author: 李金玉 多谢 ChangKai 兄。这一关假设有 n 个箱子的话,推动数大概是 n^2 数量级。
[ 本帖最后由 sokoban 于 2009-6-14 15:43 编辑 ] 对不起粗心了.
题目是我贴的答案演示到省略号时的图案. 又找到一题
level 0
#####
# + ##
##$.$ #
# * #
# * #
## ###
####
level 1
#####
# + #
#$.$#
# * ##
## * #
# * #
# * #
## ###
####
level 2
#####
# + #
#$.$#
# * #
# * #
# * ##
## * #
# * #
# * #
## ###
####
level 7
#####
# + #
#$.$#
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * ##
## * #
# * #
# * #
## ###
####
每一级增加两个箱子,只能是偶数个,奇数个无解
level0="rDrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL"
level1="rDDDLUdrrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL"
level2="rDDDLUdrDDLUdrrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuuuullDDRUldDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuuuurrDDLUdrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL"
box=2X+4=箱子个数
X|box | Total Pushes | Total Moves |
0| 4 | 15 | 48 |
1| 6 | 57 | 170 |
2| 8 | 167 | 494 |
3| 10 | 455 | 1,346 |
4| 12 | 1,209 | 3,580 |
5| 14 | 3,183 | 9,432 |
6| 16 | 8,351 | 24,756 |
7| 18 | 21,881 | 64,878 |
8| 20 | 57,303 | 169,922 |
9| 22 | 150,039 | 444,934 |
10| 24 | 392,825 | 1,164,928 |
11| 26 | 1,028,447 | 3,049,900 |
12| 28 | 2,692,527 | 7,984,824 |
13| 30 | 7,049,145 | 20,904,626 |
14| 32 | 18,454,919 | 54,729,110 |
15| 34 | 48,315,623 | 143,282,762 |
16| 36 | 126,491,961 | 375,119,236 |
17| 38 | 331,160,271 | 982,075,008 |
18| 40 | 866,988,863 | 2,571,105,852 |
19| 42 |2,269,806,329 | 6,731,242,614 |
这个比较象九连环
以下用FOXPRO写了一个解法计算程序(仅对此题),从用到两重循环可知,一定是指数级的。
************
set talk off
clear
maxn=9
DIME sa,sb,sc,sz
*Sc=""
*Sa=""
Sa="DDLUdr"
*Sb0="LUlldRdrUrruulDuullDDRUdddlUluRurrrddL"
Sc="LUdrruulDlddlUluRuuurrDDLUdrrddL"
Sb="LUlldRdrUrruulDuu"+"ll"+"DDRUdddlUluRurrrddL"+ "LUlldRdrUrruulDuu" + "uu" +"ll" +"DDRUld" +"DDRUdddlUluRurrrddL"+ Sc+ "LUlldRdrUrruulDuu"+"ll"+"DDRUdddlUluRurrrddL"
Sz="rD"+Sa+ "rddl" +Sb + "UruL"
for n=2 to maxn
Sa=fm("DDLUdr",n)
Sc="LUdrruulDlddlUluRu" + fm("uu",n) +"rr"+ Sa + "rddL"
Sb=Sb +"LUlldRdrUrruulDuu" + fm("uu",n) +"ll" +fm("DDRUld",n) +"DDRUdddlUluRurrrddL"
*Sb=Sb +Sc +Sb
Sb=Sb +Sc +"LUlldRdrUrruulDuullDDRUdddlUluRurrrddL"
FOR j=2 to n
Sb=Sb +Sc +Sb
next
Sz="rD"+Sa+ "rddl" +Sb + "UruL"
_cliptext=Sz
?"level","box","move and push"
? n,n*2+4, len(Sz)
wait
next
return
func fm(fs,fm)
fss=""
if fm>=1 then
for fi=1 to fm
fss=fss+fs
next
endif
return fss
***********
[ 本帖最后由 jinyou 于 2009-6-15 16:26 编辑 ] 谢谢jinyou兄! 不知道你的计算程序要用多少时间才算出100个箱子的推动和移动。
我对FOXPRO不认识, 不然我就自几试试。 我的程序只算了十几个箱子.100个箱子答案长度比魔方的可能状态数还多,我这种字符串累加方法,怎么能用,要是只计算长度那是很快的.极限(L/L)=2.618=(((根号5)+1)/2) * (((根号5)+1)/2) (n 对应的箱子数=2*n+4) 就是每加两个箱子将增加 黄金比例平方倍 。 31楼的关卡我有答案 50355/23300