s*****n
发帖数: 994 | 1 为啥dfs是最短solution？
题目在此
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. |
p*****2
发帖数: 21240 | |
s*****n
发帖数: 994 | 3 interviewstreet上的sample题
是多柱子，任意起点／终点
实在觉得30～40分钟写不出来啊
【在 p*****2 的大作中提到】
: F哪个？
|
p*****2
发帖数: 21240 | 4
好像就是F的那个，我以前做过，好像是用的bfs吧。
【在 s*****n 的大作中提到】
: interviewstreet上的sample题
: 是多柱子，任意起点／终点
: 实在觉得30～40分钟写不出来啊
|
a******e
发帖数: 710 | 5 请问二爷bfs大致思路是啥样子的。 有code更好
【在 p*****2 的大作中提到】
:
: 好像就是F的那个，我以前做过，好像是用的bfs吧。
|
p*****2
发帖数: 21240 | |
