题解 | #Bits#_牛客博客

题目描述

给定三根柱子和 n 个盘子（编号从大到小依次为 n 到 1），初始时所有盘子按从大到小的顺序堆叠在最左侧柱子（A柱）。要求通过一系列移动，将所有盘子转移到：

最右侧柱子（C柱）（若 n 为偶数）
中间柱子（B柱）（若 n 为奇数）

移动规则遵循经典汉诺塔：每次移动一个盘子，且小盘子必须在大盘子之上。输出需以图形化形式展示每一步的状态，每组输出包含 n+2 行，组间用分隔线隔开。

算法解析

1. 递归算法原理

汉诺塔问题的递归本质是分治策略：

基础情况：当 n=1 时，直接将盘子从源柱移到目标柱。
递归分解（n>1）：
1. 将上层 n-1 个盘子从源柱（A）经目标柱（B/C）暂存到辅助柱（B/C）。
2. 将底层第 n 个盘子从源柱（A）直接移动到目标柱。
3. 将暂存的 n-1 个盘子从辅助柱移回目标柱。
  递归式为： $T(n) = 2T(n-1) + 1$ ，总步数为 $2^n - 1$ 。

2. 目标柱选择策略

根据题目要求：

n 为偶数：目标柱为 C（最右），辅助柱为 B（中间）。
n 为奇数：目标柱为 B（中间），辅助柱为 C（最右）。

3. 图形化输出设计

图形化表示需满足以下格式：

行结构：每组输出 n+2 行：
- 第1行：全 . 填充的空白行。
- 第2行：三个柱子的顶部支架（如 ...|.....|.....|...）。
- 第3到 n+2 行：每行表示一层盘子的分布。
盘子表示：
- 盘子宽度为奇数，最大盘子宽度为 2n+1。
- 用 * 绘制盘子，| 表示柱子，. 表示空白。
组间分隔：每组后用 3×(2n+1)+4 个 - 分隔。

4. 状态维护

数据结构：使用 vector<vector<int>> cnt(4) 记录每根柱子上的盘子编号（cnt[1] 为A柱，cnt[2] 为B柱，cnt[3] 为C柱）。
移动过程：
- 初始状态：所有盘子置于 cnt[1]（A柱）。
- 递归移动：调用 hanio(n, 1, to, aux)，其中 to 和 aux 根据 n 的奇偶性确定。
- 图形更新：每次移动后调用 output() 输出当前状态。

代码实现

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> cnt(4, vector<int>(1, 0)); // 三根柱子的盘子状态（索引1~3）
bool fir = true; // 标记是否为第一组输出（避免前置分隔线）

// 检查柱子no的第line层、第col位置是否有盘子
bool chk(int no, int line, int col) {
    if (line <= (int)cnt[no].size() - 1 && cnt[no][line] / 2 >= col) 
        return true;
    return false;
}

// 输出当前图形状态
void output() {
    if (!fir) { // 非首组输出时添加分隔线
        for (int i = 1; i <= 3 * (2 * n + 1) + 4; i++) cout << "-";
        cout << "\n";
    } else fir = false;

    // 第1行：全空白行
    for (int i = 1; i <= 3 * (2 * n + 1) + 4; i++) cout << ".";
    cout << "\n";

    // 第2行：柱子顶部支架
    cout << ".";
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= n; j++) cout << ".";
        cout << "|";
        for (int j = 1; j <= n; j++) cout << ".";
        cout << ".";
    }
    cout << "\n";

    // 第3~(n+2)行：绘制每层盘子
    for (int i = 1; i <= n; i++) {
        cout << ".";
        for (int j = 1; j <= 3; j++) { // 遍历三根柱子
            // 左侧空白和盘子左半部分
            for (int k = 1; k <= n; k++) {
                if (chk(j, n - i + 1, n - k + 1)) cout << "*";
                else cout << ".";
            }
            // 柱子中心或盘子中心
            if (chk(j, n - i + 1, 1)) cout << "*";
            else cout << "|";
            // 右侧空白和盘子右半部分
            for (int k = 1; k <= n; k++) {
                if (chk(j, n - i + 1, k)) cout << "*";
                else cout << ".";
            }
            cout << ".";
        }
        cout << "\n";
    }
}

// 递归移动汉诺塔
void hanio(int sum, int from, int to, int through) {
    if (sum == 0) return;
    // 1. 将上层sum-1个盘子移到辅助柱
    hanio(sum - 1, from, through, to); 
    // 2. 移动底层最大盘
    cnt[to].push_back(cnt[from].back());
    cnt[from].pop_back();
    output(); // 输出移动后的状态
    // 3. 将上层盘子移回目标柱
    hanio(sum - 1, through, to, from); 
}

void solve() {
    cin >> n;
    int sum = 2 * n + 1; // 最大盘子宽度
    // 初始化A柱：盘子按宽度递减存放
    for (int i = 1; i <= n; i++) {
        cnt[1].push_back(sum);
        sum -= 2; // 每层盘子宽度减2（保持对称）
    }
    output(); // 输出初始状态
    // 根据n奇偶性选择目标柱和辅助柱
    if (n & 1) hanio(n, 1, 2, 3); // 奇数：目标为B柱（索引2）
    else hanio(n, 1, 3, 2);       // 偶数：目标为C柱（索引3）
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}