d734: 另類Hanoi

內容

設有 n 個大小不同的中空圓盤，按從小到大的順序從 1 到 n 編號。將這 n 個圓盤任意的迭套在三根立柱上，立柱的編號依次為 a、b、c ，這個狀態稱為初始狀態。

現在要求找到一種步數最少的移動方案，使得從初始狀態轉變為目標狀態。

移動時有如下要求：

• 一次只能移動一個盤。

• 不允許把大盤移到小盤上面。

輸入

第一行數字 n(1<=n<=20)，表示狀態中圓盤總數。

第二行表示初始狀態，有 n 個數字，第 i 個數字 a[i]表示第 i 個圓盤放在第 a[i]個立柱上。

第三行表示目標狀態，有 n 個數字，第 i 個數字 b[i]表示第 i 個圓盤放在第 b[i]個立柱上。

不必 EOF 判斷。

5
1 1 1 2 2
3 1 2 2 2

輸出

輸出移動步驟時，需按照 ring x : y -> z 的格式，其中 x 為整數，y、z 為 a、b、c 其中一個。
最後在輸出最少步數。

ring 1 : a -> b
ring 2 : a -> c
ring 1 : b -> c
ring 3 : a -> b
ring 1 : c -> b
ring 2 : c -> a
ring 1 : b -> c
7

解題思路

參考 b190，這題稍微複雜了點，起始狀態和結束狀態都是亂的，不過其實沒甚麼差，因為起始狀態不管事有序或無序處理方式都是一樣的，所以只要把原本"奇數到 b 柱、偶數到 c 柱"改成"移動到指定的柱子"就行了，解決方法也很簡單，再額外開一個陣列紀錄目標位置即可。

其他的細節請參考本題的進階版 b592。

完整程式碼

AC (66ms, 120KB)

#include <stdio.h>

int n, count, tmp;
char now[25], end[25];

void dfs(int lv, char to)
{
    for (int i = lv; i; i--)
    {
        if (lv == n)
            to = end[i];
        if (now[i] != to)
        {
            dfs(i - 1, 294 - now[i] - to);
            printf("ring %d : %c -> %c\n", i, now[i], to);
            now[i] = to;
            count++;
        }
    }
}

int main()
{
    while (scanf(" %d", &n) == 1)
    {
        count = 0;
        for (int i = 1; i <= n; i++)
            scanf(" %d", &tmp), now[i] = tmp + 96;
        for (int i = 1; i <= n; i++)
            scanf(" %d", &tmp), end[i] = tmp + 96;
        dfs(n, 0);
        printf("%d\n", count);
    }
    return 0;
}