题目链接：传送门
题目大意：
汉诺塔，给定n个盘子（n <= 45），起始状态和结束状态，求最小的步数以及路径。
思路：
考虑用dfs贪心地将剩余最大盘归位。
#include<bits/stdc++.h> using namespace std;
const int MAX_N = ;
const int SUM = ; int N, ans;
int f1[MAX_N], f2[MAX_N]; void dfs(int cur, int st, int ed, bool now)
{
int mid = SUM - st - ed;
if (st == ed) {
if (cur > )
dfs(cur-, f1[cur-], now ? f2[cur-] : ed, now);
return;
}
if (cur > )
dfs(cur-, f1[cur-], mid, false);
ans++;
printf("move %d from %c to %c\n", cur, 'A' + st, 'A' + ed);
f1[cur] = ed;
if (cur > )
dfs(cur-, f1[cur-], now ? f2[cur-] : ed, now);
} void input()
{
ans = ;
cin >> N;
for (int i = ; i < ; i++) {
int x;
cin >> x;
while (x--) {
int cur;
cin >> cur;
if (i/)
f2[cur] = i%;
else
f1[cur] = i%;
}
}
} int main(){
input();
dfs(N, f1[N], f2[N], true);
cout << ans << endl;
return ;
}
以上代码会被这组数据hack。
/*
3
1 3
0
2 2 1
2 2 1
0
1 3
*/
但是大多数情况下贪心思路没有问题，所以用模拟退火优化。
#include<bits/stdc++.h> using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX_N = ;
const int SUM = ; int N, ans, icur;
string sans, scur;
int ff1[MAX_N], ff2[MAX_N];
int f1[MAX_N], f2[MAX_N]; void mov(int cur, int st, int ed)
{
icur++;
scur += "move ";
if (cur >= )
scur += char(cur/ + '');
scur += char(cur% + '');
scur += " from ";
scur += char(st + 'A');
scur += " to ";
scur += char(ed + 'A');
scur += "\n";
} void dfs(int cur, int st, int ed, bool now)
{
int mid = SUM - st - ed;
if (st == ed) {
if (cur > )
dfs(cur-, f1[cur-], now ? f2[cur-] : ed, now);
return;
}
if (cur > )
dfs(cur-, f1[cur-], mid, false);
mov(cur, st, ed);
f1[cur] = ed;
if (cur > )
dfs(cur-, f1[cur-], now ? f2[cur-] : ed, now);
} void input()
{
ans = INF;
cin >> N;
for (int i = ; i < ; i++) {
int x;
cin >> x;
while (x--) {
int cur;
cin >> cur;
if (i/)
ff2[cur] = i%;
else
ff1[cur] = i%;
}
}
} int main(){
input();
int T = ;
srand();
while (T--) {
icur = ;
scur = "";
for (int i = ; i <= N; i++) {
f1[i] = ff1[i];
f2[i] = ff2[i];
}
for (int i = N; i >= ; i--) {
if (rand()%(i+) != )
dfs(i, f1[i], f2[i], true);
else
dfs(i, f1[i], SUM-f1[i]-f2[i], true);
}
dfs(N, f1[N], f2[N], true);
if (ans > icur) {
ans = icur;
sans = scur;
}
}
cout << sans << ans << endl;
return ;
}
/*
3
1 3
0
2 2 1
2 2 1
0
1 3
*/