POJ 3087 Shuffle'm Up：模擬籌碼洗牌過程

POJ 3087 Shuffle'm Up：模擬籌碼洗牌

有兩疊各 C 個籌碼 S1、S2，洗牌操作：從底部開始交替取 S2、S1 的籌碼疊成新疊 S12，再將 S12 底部 C 個分給新 S1，頂部 C 個分給新 S2。給定初始 S1、S2 及目標疊，求最少洗牌次數；無法達到輸出 -1。

解題思路

直接模擬洗牌過程。用陣列記錄每次洗牌後的 S12 狀態。若當前 S12 等於目標則輸出次數；若 S12 回到初始狀態（說明進入循環）則輸出 -1。注意輸入順序為從底到頂，模擬時需正確映射索引。

代碼實現

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define M 110
char mat[220], S1[M], S2[M];
char map[1000][220];
int main() {
    int n, m, i, j, x, k;
    while (scanf("%d", &m) != EOF && m) {
        for (k = 1; k <= m; k++) {
            memset(map, '0', sizeof(map));
            memset(mat, '0', sizeof(mat));
            scanf("%d%s%s%s", &n, S1, S2, mat);
            x = 1;
            while (1) {
                for (i = 0; i < n; i++) {
                    map[x][2*i] = S2[i];      // S2 放下面
                    map[x][2*i+1] = S1[i];    // S1 放上面
                }
                map[x][2*n] = '\0';
                if (strcmp(map[x], mat) == 0) break;
                for (i = 0; i < x; i++)
                    if (strcmp(map[i], map[x]) == 0) { x = -1; break; }
                for (i = 0; i <= n-1; i++) S1[i] = map[x][i];
                for (i = n; i < 2*n; i++) S2[i-n] = map[x][i];
                if (x == -1) break;
                x++;
            }
            printf("%d %d\n", k, x);
        }
    }
    return 0;
}

時間複雜度 O(狀態數 × C)，狀態數上界為 (2C)!，但實際循環極短，C ≤ 100 時極快。