Znzryb's Blog
0%

P1242 新汉诺塔

Posted on Edited on

题目大意

有 nn 个大小不同的圆盘（编号 1simn1sim n，编号越大盘越大），初始时它们以任意方式套叠在三根柱子 A,B,CA,B,C 上（输入给出每根柱子从上到下的圆盘编号；用 0 表示空）。

同样给出一个目标状态。要求在满足：

  • 每次只能移动一个圆盘

  • 不能把大盘放在小盘上

的前提下，用最少步数把初始状态变到目标状态。

输出每一步操作 move I from P to Q，最后输出最少步数。

63pts, 期待以后的自己

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <vector> 
#include <algorithm>
using namespace std;
const int maxn=50;
int n,n1,a1,now[maxn],ob[maxn]; //ob is abbreviation of object;
vector<int> hanoi[5],cache;
long long ans;
char ForOut[4]={'0','A','B','C'};
// bool vis[maxn];
//void debug(){
//	for(int i=1;i<=3;i++){
//		for(int j=0;j<hanoi[i].size();j++)
//			cout<<hanoi[i][j]<<" ";
//		cout<<endl;
//	}
//		
//}
inline void out(int st,int ed,int x){
	ans+=1;
	cout<<"move "<<x<<" from "<<ForOut[st]<<" to "<<ForOut[ed]<<endl;
}
inline bool check(int x){
	for(int i=1;i<=3;i++)
		if(!hanoi[i].empty() && x==hanoi[i].back() /*&& x<hanoi[c].back()*/ /*&& !vis[x]*/)
			return true;
	return false;
}
inline void upd(int x,int c){
	hanoi[now[x]].pop_back();
	hanoi[c].push_back(x);
	swap(now[x],c);
}
void solve(int a,int b,int c,int x){
	if(check(x)){
		if(!hanoi[c].empty() && x>hanoi[c].back()){
			solve(c,a,b,hanoi[c].back());
		}
		out(now[x],c,x);
		upd(x,c);
		return;
	}
	for(int i=x-1;i>=1;i--){
		if(now[i]==b) continue;  // If big plates on b(tool column) just ignore it 
		solve(now[i],6-now[i]-b,b,i);
	}
	out(a,c,x);
	upd(x,c);
}
bool cmp(int a,int b){
	if(a!=b) return a>b;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=3;i++){
		cin>>n1;
		for(int _=1;_<=n1;_++){
			cin>>a1;
			now[a1]=i;
			cache.push_back(a1);
		}
		sort(cache.begin(),cache.end(),cmp);
		for(int j=0;j<cache.size();j++)
			hanoi[i].push_back(cache[j]);
		cache.clear();
	}
	for(int i=1;i<=3;i++){
		cin>>n1;
		for(int _=1;_<=n1;_++){
			cin>>a1;
			ob[a1]=i;
		}
	}
	// debug();
	for(int i=n;i>=1;i--){
		if(now[i]!=ob[i])
			/*vis[i]=true,*/solve(now[i],6-now[i]-ob[i],ob[i],i);
	}
	cout<<ans<<endl;
	cin>>n;
}
// https://www.luogu.com.cn/problem/P1242
// It is clear from the above: to move K from X to Y, part of the minimum number 
// of operations must be performed so that the disc with a number less than K 
// must be moved to Z.
// 45pts https://www.luogu.com.cn/record/179798145 error because of put 6 on 5
// I add a bool vis && cache.
// the inputs are not necessary to be sorted
// 63pts https://www.luogu.com.cn/record/179814530