魔方吧·中文魔方俱乐部

标题: 从解答步骤还原关卡地图 [打印本页]

作者: skyivben 时间: 2011-7-10 13:56:33 标题: 从解答步骤还原关卡地图

我写了一个程序，可以从推箱子的解答步骤还原关卡地图。可以访问以下网页：Sokoban: Lurd to Xsb 在线使用该程序。

其算法可以参见我的博客：

作者: chzhy 时间: 2011-7-10 15:16:16

哈哈，楼主的程序和之前金优兄的程序有得一比，非常类似，试了一关，还原的地图和金优的那个一样。很好，我不懂程序，支持你！

作者: skyivben 时间: 2011-7-10 15:29:06

再来一幅图片：

作者: skyivben 时间: 2011-7-10 15:31:53 标题: 回复 2# 的帖子

谢谢您的支持。

如果您有什么意见和建议，请在这里提出，或者到博客园中我的博客中提出，以便我改进程序。谢谢！

作者: skyivben 时间: 2011-7-10 16:39:32

继续给出图片：

作者: anian 时间: 2011-7-10 23:30:15

感谢分享!

作者: sokoban 时间: 2011-7-11 09:50:04

非常好的在线工具，添加到sokoban.ws的友情连接了

作者: skyivben 时间: 2011-7-13 09:57:12

非常感谢 anian 和 sokoban 朋友的支持！

作者: anian 时间: 2011-7-13 13:23:46

skyivben兄，你的程序有个bug。 (和XhtXsb.exe有同样的bug)

请试试这个LURD： (这个LURD是我以前用来测试 LURD2XSB程序的)
UlLLUuuluLlDlldddrRRRRRRRRRRdrUllllllllllllulldRRRRRRRRRRRRRuRRlDllllllluuululldDDuulldddrRRRRRRRRRRdRRlUllllllluuulLulDDDuulldddrRRRRRRRRRRuRDllllllluuulluuurDDuullDDDDDuulldddrRRRRRRRRRRRRlllllllluuuLLulDDDuulldddrRRRRRRRRRRRldR

附件: lurd2xsb_bug.png (2011-7-13 13:24:17, 40.57 KB) / 下载次数 69
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTUwNTgzfDVkYzJhODI3fDE3MzIyNDQzMTB8MHww

作者: skyivben 时间: 2011-7-13 16:12:10

anina 兄您好，您给出的解法步骤中前六步是：UlLLUu。问题就出在第六步，因为第五步是“U”，表示推着箱子往上走一步，而第六步是“u”，表示不推箱子往上走一步，而这是不可能的，第五步中推着的箱子到哪里去了？我在“[url=http://www.cnblogs.com/skyivben/archive/2011/07/03/2096801.html]【算法】从推箱子的解答步骤还原关卡地图[/url]”这篇文章中“解法步骤不合法的情况”小节作了说明：

上面三幅关卡地图分别是从“LURD”、“Rrr”和“RL”解法步骤中还原出来的。对于这些不合法的解法步骤，本程序也不报错。本程序只保证合法的解法步骤能够还原出正确的关卡地图。此外，本程序还忽略解法步骤中“lurdLURD”以外的所有字符。

也就是说，我的程序对不合法的解法步骤并不报错(XhtXsb.exe应该也是这样)，只保证合法的解法步骤能够还原出正确的关卡地图。
当然，如果大家认为对不合法的解法步骤需要报错的话，我也可以修改程序。
感谢您的指正。

作者: anian 时间: 2011-7-13 20:39:12

我认为报错比较好。如果没有提示，我们会以为还原关卡的答案就是我们提供的LURD。但事实上是不可以过关的。

作者: rocwings 时间: 2011-7-14 14:23:12

显然不报错，问题很多啊。最简单的情况如下：
答案：UuU
关卡：
###
#.#
#$#
#.#
#$#
#@#
###

显然错了

作者: skyivben 时间: 2011-7-14 14:38:22

好吧，根据大家的意见，我将修改程序，使之在解法步骤不合法的情况给出相应的信息。

作者: skyivben 时间: 2011-7-15 22:51:33

已经修改程序，对不合法的解法步骤给出相应的提示：Invalid。如下所示：

作者: sokoban 时间: 2011-7-15 23:05:36

很喜欢用红色背景来辅助报错的设计，看上去很清楚。

作者: sokoban 时间: 2011-7-16 20:59:17

长为n的lurd串中有多少个是合法的？
在没有任何限制下，长为n的串的总数是8^n。
下面假设对一个合法的串，最后一步一定要是推，即最后一个字母只能是L,U,R,D之一。
若加上这个条件限制，长为n的串的总数为4 x 8^(n-1)

我曾经编程计算(就是对每个长为n的串都跑一遍还原关卡的算法)过比较小的n，合法的串的数目（没有详细反复验证，数字不一定对）

n       合法的串                      串的总数 4 x 8^(n-1)                         占的比例
1             4                                     4                                                       100%
2             24                                  32                                                    75%
3          156                                  256                                              60.94%
4          912                               2048                                                 44.53%
5          5536                            16384                                                 33.79%
6          31952                            13,1072                                           24.38%
7          187508                         104,8576                                           17.88%
8       1071696                         838,8608                                           12.78%
9          6168372                         6710,8864                                        9.19%
10       34972576                      5,3687,0912                                        6.51%

[ 本帖最后由 sokoban 于 2011-7-16 21:05 编辑 ]

作者: skyivben 时间: 2011-7-17 07:53:13 标题: 回复 16# 的帖子

这是一个很有趣的数学问题，而且好象也很难找到什么数学公式来计算所占的比例。
似乎也只有通过编程来计算了，那么当 n 很大时，计算所需的时间就会太长了，以致于无法完成计算。

作者: sokoban 时间: 2011-7-18 11:52:48 标题: 回复 17# 的帖子

我那破电脑算n=10就花了好几个小时。而且对 n=10 ，关卡可以说是无比平凡的，意义不大。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)