从解答步骤还原关卡地图

anian

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

rocwings

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

显然错了

skyivben

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

skyivben

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

sokoban

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

sokoban

长为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

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

sokoban

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