相 信大家都知道著名的河內塔問題。簡單來說，就是有三根柱子，柱子上可以套多個圓盤，圓盤大小都不同，但是每次移動一個圓盤的時候都不能有較大的圓盤在較小 的圓盤上。一般來說一開始的初始狀態是所有圓盤都在同一根柱子上，目標是在不違反規則的條件下，至少移動幾次圓盤可使所有圓盤移動到另外一根柱子上。

        我們的問題比較複雜一點，給定圓盤的初始狀態以及目標狀態，問至少要移動幾次能從初始狀態到目標狀態。

4
1 1 1 1
1 2 2 1
3
1 1 1
2 2 2
3
1 2 3
3 2 1
4
1 1 1 1
1 1 1 1
31
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0

6
7
3
0
147483633

2011成功高中校內賽複賽 第四題 (管理：david942j)

---

題目雖然要求一個起始狀態轉移到目標狀態的最少步數。

但是考慮一下後，先討論將一個凌亂狀態轉移到其中一個目標柱子上(與最原始問題目標相同)。

問題：凌亂狀態轉移到其中一個目標柱上的最少步數

當前有 n 個盤子，目標柱編號 c，三柱分別為 a, b, c。
考慮最大盤 n-th 盤

(1) 如果最大盤在 c 上時，則直接考慮當前有 n-1 個盤子，目標柱編號 c。
=> 明顯地知道最少步數時，這個最大盤必然不會動。

(2) 如果最大盤在 a 上，必須將剩餘 n-1 個盤子集中移動到 b，
最後將最大盤從 a 搬到 c，此時可以調用一般河內塔，將 n-1 個盤子從 b 轉移到 c。

(3) 如果最大盤在 b 上，類同於 (2) 的操作步數。

這個問題可以在 O(n) 以內完成。

問題：凌亂狀態A轉移到另一個凌亂狀態B的最少步數

一樣從最大盤 n-th 下手

(1) 對於最大盤 A[n] == B[n]，直接調用 n-1 的凌亂狀態A轉移到另一個凌亂狀態B
=> 明顯地知道最少步數時，這個最大盤必然不會動。

(2) 對於最大盤 A[n] != B[n]，令 buf 柱為非 A[n] 非 B[n] 的柱子。
先將凌亂 n-1 狀態A 般至 buf 柱 // 請使用上一個問題的定義。
再將 A-n-th 搬至 B[n] 柱，再考慮 n-1 個盤子的情況。

由於這個做法本身在 (2) 的操作時，會將 n-1 個盤子搬到同一個柱子上，不能使用 O(n) 標記，
維護一個前綴設定，來加快所有操作。

如果不這麼考慮會是 O(n^2)，加入前綴設定達到 O(n)。

#include <stdio.h>
#define mod 1000000007
int init[10005], goal[10005], n;
long long mod2[10005] = {1LL};
long long ret = 0;
int labelprefix, label;
void hanoiArbitrarily(int n, int goal) {
    if(n == 0)
        return;   
    if(labelprefix >= n) {
        init[n] = label;
        if(goal != label) {
            ret += mod2[n]-1;
            ret %= mod;
        }
        return;
    }
    if(init[n] != goal) {
        int target = 1;//temp buffer.
        if(init[n] == target)    target++;
        if(goal == target)        target++;
        if(init[n] == target)    target++;
        hanoiArbitrarily(n-1, target);// move other into buffer.
        init[n] = goal;//move n-th disk to goal.
        ret++;
        ret += mod2[n-1]-1;
        ret %= mod;
    } else {
        hanoiArbitrarily(n-1, goal);
    }
}
void hanoi(int n) {
    if(n == 0)
        return;
    if(labelprefix >= n)
        init[n] = label;
    if(init[n] != goal[n]) {
        int target = 1;
        if(init[n] == target)    target++;
        if(goal[n] == target)    target++;
        if(init[n] == target)    target++;
        hanoiArbitrarily(n-1, target);
        /*for(int i = 1; i < n; i++)
            init[i] = target;*/
        labelprefix = n-1, label = target;
        ret++;
        init[n] = goal[n];//move n-th disk to goal.
    }
    hanoi(n-1);
}
int main() {
    int i;
    for(i = 1; i < 10005; i++)
        mod2[i] = (mod2[i-1]*2)%mod;
    while(scanf("%d", &n) == 1 && n) {
        labelprefix = label = 0;
        for(i = 1; i <= n; i++)
            scanf("%d", &init[i]);
        for(i = 1; i <= n; i++)
            scanf("%d", &goal[i]);
        ret = 0;
        hanoi(n);
        printf("%lld\n", ret%mod);
    }
    return 0;
}