2299. 熊猫大厨的“竹香千层饼”挑战
1000ms
256MB
简单
递归算法
题目描述
熊猫大厨胖达蒸好了 $n$ 个大小不同的竹香千层饼，它们最初按照从小到大的顺序堆叠在盘子 A 上（小饼在上，大饼在下）。
胖达需要将这 $n$ 个千层饼全部转移到盘子 C 上，中间可以借用盘子 B。
在移动过程中，胖达必须恪守以下规则：
1. 每次只允许移动一个千层饼。
2. 任何时候，大饼都不得落在小饼上面（否则小饼会被压扁）。
请你编写程序，输出将这 $n$ 个千层饼从盘子 A 移动到盘子 C 的具体步骤。
输入格式
一行，包含一个正整数 $n$ ($1 \le n \le 8$)，表示千层饼的数量。
输出格式
多行，每行输出一次移动步骤，格式为 `源盘子-目标盘子`（例如 `A-C` 代表将最上面的饼从盘子 A 移动到盘子 C）。
样例 1
输入 (Input)
3
输出 (Output)
A-C A-B C-B A-C B-A B-C A-C
- 数据范围：$1 \le n \le 8$。
- **算法提示**：
这是一道经典的递归回溯问题（即汉诺塔问题）。对于 $n$ 个盘子，可以分为三步：
1. 将前 $n-1$ 个盘子从 A 借助 C 移动到 B。
2. 将第 $n$ 个盘子（最大的盘子）直接从 A 移动到 C。
3. 将 B 上的 $n-1$ 个盘子借助 A 移动到 C。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功