题解 P1242 【新汉诺塔】
汉诺塔之前一直没理顺，这次算是弄清楚了，顺便也写一下题解。
这里我讲的通俗一些，让我们把一个个圆盘看做一个个叠罗汉塔的人。然后现在他们都有一个想去的地方，但明显，如果直接走人的话，整个塔就倒了，当然也不能举着头顶上的人一起走（这样还能走的那是超人），所以要让他们头顶上的人先移动到别的地方去，别妨碍到他的移动。然后，由于要保证移动的次数最少，那么很明显只能先让需要移动的人中最强壮的人先移动到他想去的地方，这样才可以保证人塔不会倒。
简单介绍完毕之后，让我们用样例做个详细说明。
让我们假设有一个主持人，他按照每个人的强壮顺序进行询问他是否要移动。
主持人一个个问过来，先从5开始。
5：我不需要动，你去问下一个。
4：我也不需要动，你去问下一个。
3：我需要移动到B的位置，但我上面有人，请你让他们离开，同时你让B这个位置比我弱的都离开那里，让他们都到C这个位置再告诉我，我才能移动。
于是，主持人跑去让2到C这个位置。
2：我也很想走，但是我头上也有人，请你让他们离开，同时你让C这个位置比我弱的都离开那里，让他们都到B这个位置再告诉我，我才能移动。
于是，主持人又跑去找1，让他到B这个位置。
1：好的，我马上过去。
接着，1跑到了B这个位置，然后主持人和2说，你现在可以移动了。
2：好的，等我移动完后，麻烦你再让1到我这边来，因为3他要到B去。
等2就位后，主持人又跑到1那里告诉他移动到B。
等1移动好后，主持人跑去告诉3可以走了。
这样3就到了他该到的位置上了。
接着，主持人问2,想去哪里。
2：我想去A这个位置，但是我头上有人，请你让他们离开，同时你让A这个位置比我弱的都离开那里，让他们都到B这个位置再告诉我，我才能移动。
于是，主持人跑去让1移动到B后和2说，你可以移动了。
这样2也移动到了他想要到的地方。
最后，主持人问1想去哪。
1：我想去C，当然我是最弱的，我自己直接就可以过去。
就这样1也到达了他想去的位置。
终于，主持人可以休息一下了。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define data1 "W:\\Workspace\\data.in"
#define data2 "F:\\ACM\\data.in"
#define INF 0xfffffff
#define infinitesimal -2100000000
#define all(x) x.begin(),x.end()
#define in std::ios::sync_with_stdio(false);fstream _file;_file.open(data1,ios::in);if(_file){freopen(data1,"r",stdin);}else{_file.open(data2,ios::in);if(_file)freopen(data2,"r",stdin);}
#define mset(t, x) memset(t,x,sizeof(t))
#define lson index<<1
#define rson (index<<1) +1
#define loop(a, b, c) for(register int a=b;a<=c;a++)
#define loop2(a, b, c) for(int a=b;a>=c;a--)
#define loop3(a, b, c) for(int a=b;a<c;a++)
#define loop4(a, b, c) for(int a=b;a>c;a--)
#define maxn 50
int n, m;
int origin[maxn];
int dis[maxn];
int cnt = 0;
/**
*
* @param d 当前圆盘的编号
* @param x 当前圆盘的位置
* @param y 当前圆盘想去的位置
* @param mv 大于等于当前圆盘的是否都已经到了他想去的地方
*/
void dfs(int d, int x, int y, bool mv) {
if (x != y) {
//该圆盘需要动
int z = 1;
while (z == x || z == y) {
z++;//计算比它小的圆盘呆的位置
}
if (d > 1) {
dfs(d - 1, origin[d - 1], z, false);//让那些比当前圆盘小的都到z这个位置，别妨碍到自己
}
cnt++;//计数
cout << "move " << d << " from " << char(x + 'A' - 1) << " to " << char(y + 'A' - 1) << endl;
origin[d] = y;//移动
}
if (d > 1) {
dfs(d - 1, origin[d - 1], mv ? dis[d - 1] : y, mv);
//如果大于等于当前圆盘都已经就位了，则让下一个圆盘移动，否则让比他小的圆盘都待自己上面，不让他们妨碍到比自己大的圆盘的移动
}
}
int main() {
in;
cin >> n;
cin >> m;
int temp;
loop3(i, 0, m) {
cin >> temp;
origin[temp] = 1;
}
cin >> m;
loop3(i, 0, m) {
cin >> temp;
origin[temp] = 2;
}
cin >> m;
loop3(i, 0, m) {
cin >> temp;
origin[temp] = 3;
}
cin >> m;
loop3(i, 0, m) {
cin >> temp;
dis[temp] = 1;
}
cin >> m;
loop3(i, 0, m) {
cin >> temp;
dis[temp] = 2;
}
cin >> m;
loop3(i, 0, m) {
cin >> temp;
dis[temp] = 3;
}
dfs(n, origin[n], dis[n], true);
cout << cnt;
return 0;
}