C1067 - 汉诺塔问题
题目描述
汉诺塔问题（Hanoi Tower）是一个经典的数学问题，源于一个传说故事。传说在世界的某个寺庙中，有三根柱子，一根柱子上有64个由大到小穿孔的金盘，僧侣的任务是将所有盘子从一根柱子移动到另一根柱子上，但必须遵守以下规则：
- 每次只能移动一个盘子。
- 每次移动后，上面的盘子必须小于下面的盘子。
- 可以利用第三根柱子作为中转。
请你编程求出将A柱上的n个盘子依照规则移动到C柱子上的最少步骤数和具体每个操作步骤细节，借助于中间辅助的柱子B
我们约定圆盘从小到大编号为1, 2, ...n。即最上面那个最小的圆盘编号为1，最下面最大的圆盘编号为n。
输入格式
输入1行，为一个整数n，代表源柱子上有n个盘子，后面跟三个单字符字符，分别用空格分隔
整数n为盘子的数目，后三个字符表示三个杆子的字符编号
第1个单字符代表源柱子的标识，第2个单字符代表可以利用的辅助柱子，第3个单字符代表目标柱子
也就是将第1个单字符柱子上的n个盘子移动到第3个单字符柱子上去
输出格式
第1行，需要移动的最少的步数
接下来有若干行，每行代表一次移动的详细步骤，例如3:a->b的形式，即把编号为3的盘子从a杆移至b杆，这些数字和字符之间没有空格分隔
输入输出样例
| 输入样例 | 输出样例 |
|---|---|
| 3 a b c | 7 1:a->c 2:a->b 1:c->b 3:a->c 1:b->a 2:b->c 1:a->c |
数据范围与提示
100%的数据：$1 \le n \le 10$
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式
1. 标准输入输出模式：
直接从标准输入和标准输出读写数据，不需要使用freopen进行文件输入输出重定向
2. 文件输入输出模式（国内信奥赛输入输出模式）:
从文件中读写数据，需要使用freopen进行输入输出重定向
本题输入文件名为：C1067.in，输出文件名为：C1067.out