[ZSHOI-R1] 河外塔（简单版） - C++ 代码详解

题目背景

由于加强版不适合出 B 题，而我们又没有合适的 B 题，所以把这道题弱化了。

河内塔（又称汉诺塔）问题，就是在一块木板上有三个立柱，在柱 '1' 上放着三个圆盘，小的在上面，大的在下面（初始状态）。让被试将在柱 '1' 上的三个圆盘移到柱 '3' 上面（目标状态）。条件是：每次只能移动任何一个柱子上面的一个圆盘，但大的圆盘不能放在小的圆盘上。

通用问题解决者的解决过程即是手段——目的分析的策略。

题目描述

但是，你可能没有听过河外塔问题。虽然但是，好像并没有河外塔问题。于是，伟大的 X_Xy 决定创造一个河外塔问题。

既然是河内塔问题的延申，就得有些一样的东西：有三个柱子 'A'，'B' 和 'C' ，以及 'n' 个圆盘，其中编号为 'i' 的圆盘的半径长为 'i'，这些圆盘最开始都在 'A' 上，最终都要顺序（即从上往下从小到大）地移到 'C' 上。

既然是河内塔问题的延申，就得有些不同的东西：最开始在 'A' 上面的柱子并不是顺序的，由于这个限制，我们也不在意移动过程中的顺序，也就意味着你可以将一个大的圆盘放在小的圆盘上。

但是 X_Xy 很懒，他只想让你操作至多 '10^6' 次。

输入格式

输入共两行。

第一行有一个数 'n'，表示圆盘的数量。

第二行有 'n' 个数，表示 'A' 上所有的圆盘从上往下的标号。

输出格式

共若干行。

第一行有一个数 'tot'，表示你的操作数。

接下来的第 '2' 到第 'tot' 行，每行两个用空格隔开的大写字母，第 'i+1' 行表示你的第 'i' 次操作是从某立柱移到了另一个上。

样例 #1

样例输入 #1

3
1 2 3

样例输出 #1

5
A B
A B
A C
B C
B C

提示

对于所有数据点：'1 ≤ n ≤ 1300'。

| 数据点 | n | | :----------: | :----------: | | 1~3 | ≤ 10 | | 4~6 | ≤ 200 | | 7~10 | ≤ 1300 |

C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

vector<pair<char, char>> moves;

void move(int n, char source, char target, char aux) {
    if (n == 0) return;
    move(n - 1, source, aux, target);
    moves.push_back(make_pair(source, target));
    move(n - 1, aux, target, source);
}

int main() {
    int n;
    cin >> n;
    vector<int> disks(n);
    for (int i = 0; i < n; i++) {
        cin >> disks[i];
    }
    move(n, 'A', 'C', 'B');
    cout << moves.size() << endl;
    for (auto move : moves) {
        cout << move.first << " " << move.second << endl;
    }
    return 0;
}

代码详解

moves 数组： 用来存储移动操作，每个元素是一个 pair<char, char>，表示从哪个柱子移动到哪个柱子。
move 函数： 递归函数，用于实现汉诺塔问题的移动逻辑。参数分别为：
- n: 剩余需要移动的圆盘数量。
- source: 源柱子。
- target: 目标柱子。
- aux: 辅助柱子。
main 函数：
- 读取输入：输入圆盘数量 'n' 和圆盘顺序。
- 调用 move 函数进行移动操作。
- 输出操作数和每个移动操作。

总结

这道题的关键在于理解汉诺塔问题的递归解法，并将它应用于代码实现。代码中使用 moves 数组记录移动操作，方便输出结果。

希望本文对您理解并解决这道题目有所帮助！