POJ 1920 Towers of Hanoi：漢諾塔狀態最少步數與目標柱判斷

題目大意

給定 n 個圓盤在三根柱子上的任意合法狀態，求將所有圓盤移動到同一根柱子所需的最少步數，並輸出最終所在柱子編號。答案對 1,000,000 取模。

核心洞察：逆向思維

從給定狀態到目標狀態難以分析，但從目標狀態反推到給定狀態很容易：

• 將 i 個圓盤從一柱移到另一柱，需 2^i - 1 步（標準漢諾塔）
• 最大的圓盤 n 不動，最終目標柱必為其當前所在柱
• 遞推處理次大圓盤 n-1、n-2 ... 1

遞推邏輯

now = pos[n];           // 當前已處理圓盤所在柱（最大盤所在柱）
ans = 0;
for i = n-1 down to 1:
    need = pos[i];      // 圓盤 i 當前所在柱
    if (need != now) {  // 需要移動
        ans += 2^(i-1); // 將 1~i-1 盤移到第三柱(1步) + 移動 i(1步) + 移回(2^(i-1)-1步) = 2^(i-1)
        now = 6 - need - now; // 1~i-1 盤移至剩下的第三根柱
    }
    // else: 圓盤 i 已在正確柱，無需移動，now 不變
// 循環結束，now 即為最終目標柱（等於 pos[n]）

完整代碼

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

const int MOD = 1000000;
int pos[100005], pow2[100005];

int main() {
    pow2[0] = 1;
    for (int i = 1; i <= 100000; i++)
        pow2[i] = (pow2[i-1] * 2) % MOD;

    int n;
    while (cin >> n) {
        int x[4];
        scanf("%d%d%d", &x[1], &x[2], &x[3]);
        for (int i = 1; i <= 3; i++)
            for (int j = 0, a; j < x[i]; j++) {
                scanf("%d", &a);
                pos[a] = i; // 圓盤 a 在柱 i
            }

        int now = pos[n];
        int ans = 0;
        for (int i = n-1; i >= 1; i--) {
            if (pos[i] != now) {
                ans = (ans + pow2[i-1]) % MOD;
                now = 6 - pos[i] - now; // 第三根柱：1+2+3=6
            }
        }
        cout << pos[n] << endl << ans << endl;
    }
    return 0;
}

關鍵點解析

1. 目標柱確定：最大盤 n 從不移動（移動它需先移走所有較小盤，得不償失），故最終柱 = pos[n]
2. 步數公式：移動第 i 盤需 2^(i-1) 步，預處理 pow2 陣列取模
3. 第三根柱計算：三柱編號 1,2,3，和為 6，第三柱 = 6 - a - b
4. 模運算：每步加模，避免溢出

複雜度

• 時間：O(n) 每測試案例
• 空間：O(n)

樣例驗證

輸入：n=3, 柱1: 3, 柱2: 1 2, 柱3: (空)
狀態：盤3在柱1，盤2、1在柱2
目標柱 = 1
i=2: pos[2]=2 ≠ now=1 → ans+=2, now=3
i=1: pos[1]=2 ≠ now=3 → ans+=1, now=1
總步數 = 3，最終柱 = 1 ✓