題意#
這是一道經典題目「河內塔」。
共有三根柱子（編號 1、2、3），一開始有 \( n \) 個大小不同的盤子，由大到小疊在第 1 根柱子上。
目標是將所有盤子搬到第 3 根柱子上。
規則如下：每次只能搬動某根柱子最上面的一顆盤子，且大的盤子不能放在小的盤子上。
求最少需要搬動幾次，並印出每一步的詳細過程。
思路#
狀態互相依賴的問題可以透過遞迴（Recursion）來解決。
除了常見的 hanoi(n, from, to, aux) 參數傳遞法，我們也可以透過陣列直接維護盤子狀態。
我們宣告一個陣列 v，其中 v[i] 紀錄「第 \( i \) 個盤子目前所在的柱子」。
因為所有盤子都在起點，所以初始值均為 1。
接著設計一個遞迴函數 dfs(lv, to)，其目標是「將大小從 1 到 lv 的盤子，搬遷至 to 柱子上」。
遞迴的執行過程是從大盤子往小盤子檢查：
如果盤子 i 尚未在目標柱子 to 上，我們必須先將它上方較小的盤子移走。
這些小盤子必須搬至另一根「備用柱子」。
因為三根柱子的編號和為 \( 1+2+3=6 \)，
備用柱子的編號可以直接用 6 - v[i] - to 算出。
等上方淨空後，再將盤子 i 搬移至目標，並記錄操作與更新狀態陣列。
這種紀錄狀態的寫法，在面對初始狀態非規律的變形河內塔時也能適用。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
int n, cnt = 0; // cnt 紀錄總共搬動了幾次
vector<int> v; // v[i] 隨時追蹤第 i 個盤子目前待在哪根柱子上
vector<pair<int, int>> g; // g 負責記錄具體的搬移步驟
void dfs(int lv, int to) {
// 從大盤子往小盤子掃描，把它們通通搬到目標柱子 to
for (int i = lv; i; i--) {
if (v[i] != to) { // 發現第 i 個盤子還不在目標位置上
// 必須先把它頭頂上比較小的盤子，強行全清空並搬去「備用柱子」
// 備用柱子編號的推算黑魔法：6 減去當前柱子編號，再減去目標柱子
dfs(i-1, 6-v[i]-to);
g.pb({v[i], to}); // 紀錄盤子 i 的成功搬遷路徑
v[i] = to; // 切實更新盤子 i 的駐紮地狀態
cnt++; // 累積每一次的搬移次數
}
}
}
signed main() { WA();
cin >> n; // 讀取最一開始盤子的總數量
v.assign(n+1, 1); // 初始化：所有盤子一開始都穩穩疊在第 1 根柱子上
dfs(n, 3); // 發動遞迴，要求把前 n 個盤子全數送往第 3 根柱子
cout << cnt << '\n'; // 輸出這段旅程總共耗費的步數
for (auto i : g) cout << i.fi << ' ' << i.se << '\n'; // 一行一行如實印出操作紀錄
}
