[数据结构与算法]2022蓝桥模拟-子汉诺塔

问题描述

小蓝很喜欢玩汉诺塔游戏。
游戏中有三根柱子，开始时第一根柱子上有 n 个圆盘，从上到下圆盘的大小依次为 1 到 n。
每次，可以将一个盘子从一根柱子上移动到另一根柱子上，这个盘子必须是柱子最上方的盘子，而且移到的柱子上的盘子必须比这个盘子大。
小蓝的目标是将所有的盘子移动到第三根柱子上。
汉诺塔是个经典问题，当盘子数量为 n 时，最少需要移动 $2^n?1$ 步，其中 $2^n$ 表示 2 的 n 次方。
小蓝已经玩了一会儿（不一定按最优方案玩），他想知道，对于他目前的局面，最少还需要多少步可以到达目标。

输入格式

输入的第一行包含三个非负整数 a, b, c，分别表示目前每根柱子上的盘子数。在本题中，n=a+b+c。
第二行包含 a 个整数，相邻的整数之间使用一个空格分隔，表示第一根柱子上的盘子，盘子按从上到下（从小到大）的顺序给出。
第三行包含 b 个整数，相邻的整数之间使用一个空格分隔，表示第二根柱子上的盘子，盘子按从上到下（从小到大）的顺序给出。
第四行包含 c 个整数，相邻的整数之间使用一个空格分隔，表示第三根柱子上的盘子，盘子按从上到下（从小到大）的顺序给出。

输出格式

输出一行包含一个整数，表示答案。

样例输入

1 2 3
1
2 3
4 5 6

样例输出

7

评测用例规模与约定

对于 30% 的评测用例，2 <= n <= 5。
对于所有评测用例，2 <= n <= 60。

递归C++

本题还是一个递归问题，不过依据题意来看，会出现其中几块汉诺塔已经放好的情况，我们需要分几个情况讨论。

1. 当盘子已经在第k个杆子上时，递归处理n-1个盘子
2. 如果第n个盘子不在第k个杆子上，我们需要：
   1）将前n-1个盘子移动到既不在第k个杆子，也不在第n个盘子所在杆子上；
   2）将第n个盘子移动到k杆；
   3）根据题意，当盘子数量为 n 时，最少需要移动 $2^n?1$ 步。我们把剩余的n-1个盘子移动到k需要$2^{n?1}?1$步

#include <iostream>
using namespace std;
typedef long long LL;
int a, b, c, n;
int d[4][100], p[100];

 // 计算将1-n个盘子移动到k需要多少步
LL dfs(int n, int k) {
	if (n == 0) return 0;
	if (p[n] == k) return dfs(n-1, k);
	return dfs(n-1, 6 - k - p[n]) + (1LL << (n-1));
}

int main() {
	cin >> a >> b >> c;
	
	for (int i = 0; i < a; i++) {
		cin >> d[1][i];
		p[d[1][i]] = 1; // 记录盘子在哪个杆子上
	}
	
	for (int i = 0; i < b; i++) {
		cin >> d[2][i];
		p[d[2][i]] = 2;
	}
	
	for (int i = 0; i < c; i++) {
		cin >> d[3][i];
		p[d[3][i]] = 3;
	}
	n = a+b+c;
	
	cout << dfs(n, 3) << endl;
	
	return 0;
}