提交统计

做了此题的人还做了哪些题

汉诺塔(二)

时间限制:3000 ms  |  内存限制:65535 KB
难度:5
描述

汉诺塔的规则这里就不再多说了,详见题目:汉诺塔(一)

现在假设规定要把所有的金片移动到第三个针上,给你任意一种处于合法状态的汉诺塔,你能计算出从当前状态移动到目标状态所需要的最少步数吗?

输入
第一行输入一个整数N,表示测试数据的组数(0<N<20)
每组测试数据的第一行是一个整数m表示汉诺塔的层数(0<m<32),随后的一行有m个整数Ai,表示第i小的金片所在的针的编号。(三根针的编号分别为1,2,3)
输出
输出从当前状态所所有的金片都移动到编号为3的针上所需要的最少总数
样例输入
2
3
1 1 1
3
1 1 3
样例输出
7
3
来源
[张云聪]原创
上传者
张云聪