小编Ser*_*maz的帖子

上个星期五,在法国节目比赛中,我们得到了纸张折叠问题,如下:

• 给定一张方纸和一个折叠图案,写一个函数"折叠(图案)",它将给出图纸的累积折叠(一半)所产生的图层顺序."

这可能不是很清楚,所以让我解释一下(方便一张纸可能有助于理解,如果你愿意走那么远来帮助我:)).

假设我们有一张正方形纸,我们绘制一个N*N网格,然后对其所有内部正方形进行编号.给定一个"LTRB"模式,我们将这张纸垂直折叠成两半,并将左边的部分放在右边.然后,我们将水平折叠并将顶部放在底部.然后,我们将它再次垂直折叠并将右侧部分放在左侧部分上.最后,我们将水平折叠并将底部放在顶部.这给我们留下了一张纸,大小为一平方和N ^ 2层.预期答案是每个原始正方形的结果顺序.

例如,如果我们在一张方形纸上绘制一个2*2网格,然后将每个内部正方形从1到4(从左上到右下,水平)编号,并给出模式"LT",我们就会有发生这种情况:

fold("LT"):

 1 | 2   L  1,2  T
---|--- ==> --- ==> 2,1,3,4
 3 | 4      3,4

并使用"RB"模式,例如:

fold("RB"): 

 1 | 2   R  2,1  B
---|--- ==> --- ==> 3,4,2,1
 3 | 4      4,3

正如您可能已经猜到的那样,它基本上归结为N*N矩阵的递归变换.这是最简单的部分,这是我的解决方案:

http://ideone.com/QaXGq

现在是有趣的部分.

• 编写一个函数展开(order),对于给定的结果层排序,它将给出产生这种排序的模式.请注意展开(折叠("LRTB"))=>"LRTB"

然后我的大脑停止工作了一段时间,我没有时间(总共4小时还剩2小时)来提出足够快的解决方案.

我最初的想法是:

1. 试着暴力吧.因为我们知道输入的长度是N ^ 2,所以我们可以创建一个初始矩阵并尝试所有可能的折叠,直到我们达到与输入相同的顺序.O(4 ^ N)复杂性,不可行.

2. 蛮力逆转.从输入开始,尝试所有展开的可能性,直到我们达到正确的初始状态.好一点,但仍然太慢.

3. ???

有人有想法吗？