e***n
发帖数: 42 | 1 既然是样题，希望能公开讨论一下：这道题像careercup书上Hanoi Tower的一个变形：
There are K pegs. Each peg can hold discs in decreasing order of radius when
looked from bottom to top of the peg. There are N discs which have radius 1
to N; Given the initial configuration of the pegs and the final
configuration of the pegs, output the moves required to transform from the
initial to final configuration. You are required to do the transformations
in minimal number of moves.
A move consists of picking the topmost disc of any one of the pegs and
placing it on top of anyother peg.
At anypoint of time, the decreasing radius property of all the pegs must
be maintained.
Constraints:
1<= N<=8
3<= K<=5
Input Format:
N K
2nd line contains N integers.
Each integer in the second line is in the range 1 to K where the i-th
integer denotes the peg to which disc of radius i is present in the initial
configuration.
3rd line denotes the final configuration in a format similar to the initial
configuration.
Output Format:
The first line contains M - The minimal number of moves required to complete
the transformation.
The following M lines describe a move, by a peg number to pick from and a
peg number to place on.
If there are more than one solutions, it's sufficient to output any one of
them. You can assume, there is always a solution with less than 7 moves and
the initial confirguration will not be same as the final one.
Sample Input #00:
2 3
1 1
2 2
Sample Output #00:
3
1 3
1 2
3 2
Sample Input #01:
6 4
4 2 4 3 1 1
1 1 1 1 1 1
Sample Output #01:
5
3 1
4 3
4 1
2 1
3 1
NOTE: You need to write the full code taking all inputs are from stdin and
outputs to stdout
If you are using "Java", the classname is "Solution"
比如输入：
N=6 K=4
start: 4 2 4 3 1 1
finish:1 1 1 1 1 1
我的想法是从高位开始(i=N-1)：如果start和finish pegs相同e.g.（1，1）则不需任
何操作。如果不同（e.g.3，1）则move（from start[i] to end[i]) 但是move之前要
检查后面是否有相同的case e.g. （4，1） 出现过两次，遇到这种情况要先找到一个
空的peg,（e.g.3) 做Hanoi Tower的 操作（e.g. move (from-4, to-3 m-1) m 是重复
case的个数 (对于4,1 case m=2). 然后 move(from-4, to-1, 1), 再继续下面的 （2
，1） 直到遇到下一个（4，1）的case。。。
感觉这样做很复杂，在规定的时间（45分钟)不可能完成coding。 请高手指点思路。 | B******5
发帖数: 4676 | 2 题好难，不过感觉是Breadth first search
45分钟coding出来难度不小。。。
when
1
must
【在 e***n 的大作中提到】
: 既然是样题，希望能公开讨论一下：这道题像careercup书上Hanoi Tower的一个变形：
: There are K pegs. Each peg can hold discs in decreasing order of radius when
: looked from bottom to top of the peg. There are N discs which have radius 1
: to N; Given the initial configuration of the pegs and the final
: configuration of the pegs, output the moves required to transform from the
: initial to final configuration. You are required to do the transformations
: in minimal number of moves.
: A move consists of picking the topmost disc of any one of the pegs and
: placing it on top of anyother peg.
: At anypoint of time, the decreasing radius property of all the pegs must
| v***a
发帖数: 365 | 3 I guess dfs is OK, since totally less than 7 moves |
|
