a268: 河內塔問題

2019-08-19

內容

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

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

輸入

每個測資檔包含多筆測資。每筆測資包含三行，第一行是一個正整數 N (1<=N<=10000)，代表圓盤的個數。第二行及第三行分別代表圓盤的初始與目標狀態。每行有 N 個正整數，第 i 個數 Si 代表第 i 小的圓盤是套在 Si 上，其中 Si 只可能是 1 或 2 或 3。當 N=0 時代表輸入結束。

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

輸出

對每筆測資輸出一行，代表從初始狀態到目標狀態至少要移動幾次圓盤。由於答案可能很大，請輸出 mod 1,000,000,007 的結果。

6
7
3
0
147483633

解題思路

b592 的進化版，一樣的解題邏輯就不再寫一遍了。

這題雖然測資比較變態，但只要演算法沒錯、該建的表有建、不要做多餘的操作，時間壓力並不大。

完整程式碼

AC (21ms, 148KB)

#include <stdio.h>
#define MAX 10001
#define MOD 1000000007

int steps, step[MAX] = { 1 }, n, base;
char now[MAX], to[MAX], end[MAX], curr;

int main()
{
    for (int i = 1; i < MAX; i++)
        step[i] = (step[i - 1] << 1) % MOD;
    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 = (steps + step[base]) % MOD, 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 = (steps + step[i - 1]) % MOD;
            }
            printf("%d\n", steps);
        }
        else
        {
            puts("0");
        }
    }
    return 0;
}