有一个int数组arr其中只含有1、2和3，分别代表所有圆盘目前的状态，1代表左柱，2代表中柱，3代表右柱，arr[i]的值代表第i+1个圆盘的位置。比如，arr=[3,3,2,1]，代表第1个圆盘在右柱上、第2个圆盘在右柱上、第3个圆盘在中柱上、第4个圆盘在左柱上。如果arr代表的状态是最优移动轨迹过程中出现的状态，返回arr这种状态是最优移动轨迹中的第几个状态。如果arr代表的状态不是最优移动轨迹过程中出现的状态，则返回-1。 给定一个int数组arr及数组的大小n，含义如题所述，请返回一个int，代表所求的结果。 测试样例： [3,3] 返回：3
#include
#include
#include
using namespace std;
//这是一个不断缩小的子问题，考虑1到n-1时，说明第n个圆盘已经放好了
class Hanoi
{
private:
int chk(const vector
{
if(1==k)
{
if(from==arr[k-1])return 0; //只有一个圆盘且在from上那么就在最初状态
if(to == arr[k-1])return 1; //只有一个圆盘且在to上那么就在最终状态(只有一个圆盘只需一步)
return -1;
}
if(arr[k-1] == pass) //最大那个圆盘是不可能经过辅助塔的
{
return -1;
}
//当前最大的为第k个盘，初始位置位于当前的from上，
//若所给状态其也在from上，那么说明其没有移动过，不必考虑他，直接考虑子集1到k-1
if(arr[k-1] == from)
{
return chk(arr, k-1, from, to, pass);
}
//当前最大的为第k个盘，初始位置本应在from上但给出的状态是在to上，说明其发生了移动，我们把移动分为两部分，
//一部分是把1到k-1移到pass上，第k个移到to上，第二部分为后续移动到达给定状态，
//其中第一部分需要 1<<(k-1)步，第二部分是在从pass经from到to时形成的一个过程
if(arr[k-1]==to)
{
int tmp = chk(arr, k-1, pass, from, to);
if(-1==tmp)
{
return -1;
}
return (1 << k-1)+tmp;
}
}
public:
int chkStep(vector
{
if(n<=0)return -1;
if(arr.size()!=n)return -1;
if(arr[n-1]==2)return -1; //n-1也即最大的那个盘不可能会在第二个塔位上(最优路径下)
return chk(arr, n, 1, 2, 3);
}
};
int main()
{
vector
arr.push_back(3);
arr.push_back(3);
Hanoi h;
cout << h.chkStep(arr, 2) << endl;
system("pause");
return 0;
}
