PUZZLEUP 2015

lugionline

newkid 发表于 2015-10-27 02:45
我总算看懂了，果真是巧夺天工，决定送你一个章！随便挑吧。
K+1时候的抽屉原理还有点想不通，我相信再花 ...

多谢，那就来朵跳舞的小花吧，我要 铁扇公主

证明是最大解：
二维的情况，M^2个点，如果要找出M+1个解来，必定有两个同行/同列 所以矛盾
K+1维的情况，如果有 M^K + 1 个解，必定存在 M^(K-1) + 1 个解，这些解最后一位相同
   这和 K维的结论矛盾，归纳法证明

newkid

已转一朵小红花。

newkid

#14 JUMPING PAWNS

There is a 1x20 board and 10 pawns are placed on the leftmost squares. Your task is to move these 10 pawns to the rightmost squares in minimum steps.

A step consists of either a MOVE or a JUMP

-MOVE: Pawn can move to the empty adjacent square to its right.
-JUMP:Pawn can jump over adjacent right pawn to the next square if it is empty. Jumping must continue till the pawn can't jump.

What is te minimum number of steps to accomplish this task?

If the probem was asked for 1x6 board and 3 pawns, then the answer would be 5:




有一个1X20棋盘，10个卒子方在最左边的方格中。你的任务是用最少的步骤将这些10卒走到最右边的方格中。

一个步骤或者是移动，或者是跳跃。

移动：卒子可以移动到其右侧的相邻空位。
跳跃：卒子可以越过相邻的卒子跳到下一个方格，如果这个位子是空位的话。跳跃必须持续，直到跳不动。

完成此任务的最少步骤是几步？

如果问的是1X6棋盘和3个卒子，那么答案将是5：

0:PPP***
1:PP*P**
2:*P*PP*
3:**PPP*
4:**P*PP
5:***PPP

newkid

简单粗暴的解法：总共C(20,10)个点，把所有变化找出来，然后用Dijkstra算法。

lugionline

答案是不是  M-1 ？ 如果 M 表示棋盘长度，并且是偶数，而且棋子是 M/2的话。  另外 M = 4 是特列

newkid

lugionline 发表于 2015-10-29 18:31
答案是不是  M-1 ？ 如果 M 表示棋盘长度，并且是偶数，而且棋子是 M/2的话。  另外 M = 4 是特列

怎么推算出来的，也是归纳法？
我的程序还没写呢。

lugionline

newkid 发表于 2015-10-29 23:11
怎么推算出来的，也是归纳法？
我的程序还没写呢。

没有，我只是算出结果后发现有这个规律

newkid

lugionline 发表于 2015-10-30 08:18
没有，我只是算出结果后发现有这个规律

算到18你还是对的：

dist=17
000000000111111111
000000001011111111
000000011010111111
000000101010111111
000001101010101111
000010101010101111
000110101010101011
001010101010101011
011010101010101010
011010101010101100
101010101010101100
111010101010101000
111010101010110000
111110101010100000
111110101011000000
111111101010000000
111111101100000000
111111111000000000

PL/SQL procedure successfully completed.

Elapsed: 00:00:28.83

路径输出是反序的，要从下往上看。

newkid

wiki扒下来的原版算法，要花十分钟：

dist=19
00000000001111111111
00000000010111111111
00000000110101111111
00000001010101111111
00000011010101011111
00000101010101011111
00001101010101010111
00010101010101010111
00110101010101010101
00110101010101010110
01010101010101010110
11010101010101010100
11010101010101011000
11110101010101010000
11110101010101100000
11111101010101000000
11111101010110000000
11111111010100000000
11111111011000000000
11111111110000000000

PL/SQL procedure successfully completed.

Elapsed: 00:09:47.71

lugionline

这题用A*会快很多，不过我也没有用A*，用逐步推进大概20秒