首页 > 代码库 > Hanoi

Hanoi

【题目描述】

现有个N圆盘和N个柱子,每个圆盘大小都不一样,大的圆盘不能放在小的圆盘上面,N个柱子从左到右排成一排。每次可以将一个柱子最上面的圆盘移动到右边或者左边的柱子上(移动合法)。

现给定初始时的状态,询问将第i大的圆盘移动到第i根柱子上所需的最小步数是多少。

【输入描述】

第一行输入一个正整数T,表示询问的组数;

接下来T组数据,每组数据输入格式如下:

第一行输入一个整数N;

接下来一行输入N个正整数,表示每个柱子上的圆盘大小。

【输出描述】

对于每组测试数据,输出一行,包含一个整数,表示每次的答案,如果不存在答案,输出“-1”。

【样例输入】

4

3

2 1 3

2

7 8

2

10000 1000

3

97 96 95

【样例输出】

4

0

-1

20

【数据范围及提示】

对于70%的数据,N的值相同;

对于100%的数据,1 ≤ T ≤ 6*103,1 ≤ N ≤ 7。

Hanoi