Test Message

b592: The Tower of Hanoi

本題和 a268 基本上是同一題，只是那題測資比較變態要取 MOD，但題目是敘述是中文，可以移駕過去看完題目再回來解。

內容

The Tower of Hanoi problem is a popular one in computer science. Briefly speaking, the problem is to transfer all the disks from peg-A to peg-C using peg-B as intermediate one in such a way that at no stage a larger disk is above a smaller disk. The minimum number of moves is required for this task.

It is so well studied that one can find the sequence of moves for smaller number of disks such as 3 or 4. A trivial computer program can find the case of large number of disks also. Here we have made your task little bit difcult by making the problem more flexible. Here the disks can be placed in any peg initially.

If more than one disk is in a certain peg, then they will be in a valid arrangement (larger disk will not be on smaller ones). We will give you two such arrangements of disks. Your task is to find out the minimum number of moves which will transform the first arrangement into the second one. Of course you always have to maintain the constraint that smaller disks must be upon the larger ones.

輸入

The input data consists of several test cases. Each test case contains three lines.

The first line contains a positive number n, 1 <= n <= 30, which denotes the number of disks. The two arrangements are denoted by the next two lines. Each arrangement will be represented by n integers. The value of integer is 1, 2 or 3, which denote the disk is placed in peg-A, peg-B and peg-C respectively. For example, if the i-th (1 <= i <= n) integer is 1, the i-th disk is in peg-A. The figure shown below is an example of test case. It can be described as follows and the minimum number of moves is 6.

4
1 1 1 1
1 2 2 1

img1

Input is terminated by a case where the value of n is zero. This case should not be processed.

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
0

輸出

For each test case, output the minimum number of moves as specified in the problem statement.

6
7
3
0

解題思路

本題要使用 DP 來做，所以先我們把規律整理好。

河內塔的規律

  1. 由於大盤絕不在小盤上面的關係，所以每一柱都會是排序好的，只是中間會有空缺。

  2. 當你要將一個高度為 n 的塔完整地從 A 柱移動至 B 柱時的最少步驟必為 2n - 1
    Ex: 移動高度為 3 的塔

    零　　　　一　　　　二　　　三　　　　四　　　　五　　　　六　　　七
    1 x x 　　 x x x 　　 x x x 　　 x x x 　　 x x x 　　 x x x 　　 x x x 　　 x 1 x
    2 x x 　　 2 x x 　　 x x x 　　 x x 1 　　 x x 1 　　 x x x 　　 x 2 x 　　 x 2 x
    3 x x 　　 3 1 x 　　 3 1 2 　　 3 x 2 　　 x 3 2 　　 1 3 2 　　 1 3 x 　　 x 3 x

    會是 2n-1 是因為每要移動高度為 n 的塔，都必須先把高度為 n-1 的塔搬開，移動盤子 n，再把搬開的 n-1 塔般回 n 上，而要移動盤子 n-1 又要移動 n-2 塔…以此類推直到 n 為盤子 1 時，移動他只需要一步(上面沒有盤子了)，接者再逆推回去
    n = 2 塔：[塔 1] + 1 + [塔 1] = 1 + 1 + 1 = 3、
    n = 3 塔：[塔 2] + 1 + [塔 2] = 3 + 1 + 3 = 7、
    n = 4 塔：[塔 3] + 1 + [塔 3] = 7 + 1 + 7 = 15、
    之後以此類推 ([]為移動該塔的步驟數)
    然後就能發現 塔 n = 2n-1 * 2 + 1 也就等於 2n - 1。

  3. 想移動下面的盤子一定要先把上面的盤子都移開，所以最下面的盤子一定是最後一個動的。

  4. 因為河內塔只有三根柱子、且大盤不能放到小盤上，所以如果你要把第 n 盤從 A 柱移動到 B 柱時，那你就必須要把所有比 n 還小的盤子都放到 C 柱上，換句話說，所有比 n 小的盤子都必須要移動到不是盤子 n 原本的柱或目標柱(也就是剩下的那柱)，而如果 n 原本的柱子就是目標柱，那就要把比 n 小的盤子堆到 n 所在的柱子上，維持塔的完整性，這樣之後下面的盤子才動的了。

  5. 承 1 和 4，既然已經排序好、且比 n 小的都在 C 柱上，那 C 柱就一定會有一個 n-1 的子塔(從 n-1 ~ 1，排好、且中間無空缺的塔)

規律分析

  1. 因為最下面的最後才能動，所以 DP 要由上而下

  2. 每要移動 n 就會把 n 以上的盤子堆成一座 n-1 的子塔

  3. 隨著不斷的 DP，要移動的就越底層，子塔就會越高

  4. n 子塔的位子要在 不是 n+1 盤子的位子或目的地的最後一處，如果盤子的位置和目的地相同，那 n 子塔則也要和他們在相同位子，這裡有個技巧，用如果用 1,2,3 來表示柱子，這時候

    [n 子塔的位子] = 6 - [n-1 盤當前位子] - [n-1 盤目標位子]

    至於原因…因為 1 + 2 + 3 = 6，所以 6 減任意兩數(柱)就必然會剩下最後一個沒被用到的數(柱)，而當 6 - 2 - 2 時輸出為 2，一樣符合條件，不過 當前位子 = 目標位子 的情況在實作時都會在前面被過濾掉就是了。

  5. 所以 DP 要做的就是從底部開始找出每層的目標位置，再從頂部開始把每層移動至目標位置 (子塔會在配合移動時越建越高，最後高度必是底部 - 1 ~ 1)。

到此為止是快速求出混亂河內塔還原回一個完整塔所需步驟的方法，但根據題目的目標也可能是混亂的，所以排好之後又要打亂，但好消息是打亂遠比還原輕鬆得多，從底部開始，如果”盤 n”的目標柱跟當前柱不一樣，就把”塔 n-1”搬到剩下的柱，把”盤 n”移至目標位置，如此反覆直到最頂層即可。

一些雜項

  1. 本題 DP 的其實就是這 4 個部分 : 做好的子塔的高度和位置、要移動的盤子的初始位置和目標位置，然後從上到下排好、再從下到上放到目標位置。

  2. 從頂層開始起始陣列有可能會連續好幾個一樣
    Ex:

    1 x x
    2 x x
    3 x x
    x 4 x
    x x 5

    這時候直接把 3 開始當子塔可以省掉一些判斷時間。

  3. 從底部開始陣列有可能起始位置 = 目標位置，這些都是不用排的，一樣可以在開始過濾掉。

  4. 雖然上面多次提到要移動子塔，但由於子塔一定只會在某一柱上，所以不用真的把陣列的元素都改到子塔位置，用一個元素代表子塔位置即可。

  5. 河內塔邏輯比較複雜，多用紙筆模擬幾次情境會比較好理解上述的規律和流程。

完整程式碼

AC (1ms, 88KB)
#include <stdio.h>

unsigned long long steps;
int step[35], n, base;
char now[35], to[35], end[35], curr;

int main()
{
    for (int i = 0; i < 31; i++)
        step[i] = 1 << i;
    while (scanf(" %d", &n) == 1 && n)
    {
        steps = 0, base = 1;
        for (int i = 1; i <= n; i++)
            scanf(" %d", &now[i]);
        for (int i = 1; i <= n; i++)
            scanf(" %d", &end[i]);
        while (now[n] == end[n] && n)
            n--;
        if (n)
        {
            while (now[base + 1] == now[1] && base < n - 1)
                base++;
            to[n] = end[n];
            for (int i = n; i > 1; i--)
                to[i - 1] = now[i] == to[i] ? to[i] : 6 - now[i] - to[i];
            curr = now[base];
            for (int i = base + 1; i <= n; i++)
            {
                if (now[i] == to[i]) continue;
                if (now[i] + to[i] + curr == 6)
                    steps++;
                else
                    steps += step[base], base = i - 1, curr = 6 - now[i] - to[i];
            }
            curr = to[n - 1];
            for (int i = base; i; i--)
            {
                if (curr == end[i]) continue;
                curr = 6 - curr - end[i];
                steps += step[i - 1];
            }
            printf("%llu\n", steps);
        }
        else
        {
            puts("0");
        }
    }
    return 0;
}