UVA 716 Commedia dell'arte：三維數碼拼圖可解性判斷

UVA 716 Commedia dell'arte：三維 N-數碼問題的奇偶性判定

給定 n×n×n 的三維拼圖，判斷能否通過移動空格將數字排為有序（最後位置為空）。移動規則：空格可與相鄰 (共面) 位置交換。

推廣二維結論到三維

• 二維：n 奇時，逆序對奇偶性 + 空格行號奇偶性 不變；n 偶時，逆序對奇偶性 + 空格行號奇偶性 改變。
• 三維：Z 軸移動相當於 n²-1 次交換，Y 軸移動相當於 n-1 次交換，X 軸移動不變。逆序對奇偶性改變規律與二維相同。

判定條件

• n 為奇數：逆序對數為偶數 → 可解；奇數 → 不可解。
• n 為偶數：設空格需移動到終點的 Y、Z 方向步數和為 bu，則 (bu ^ 逆序對奇偶性) == 0 → 可解；否則不可解。

代碼實現 (C++)

#include <cstdio>
#include <cstring>
const int N = 1000005;
typedef long long ll;
int t, n, a[N], save[N], v;

ll merge_count(int *a, int l, int r) { // 歸併排序求逆序對
    if (l >= r) return 0;
    int mid = (l+r)/2;
    ll ans = merge_count(a, l, mid) + merge_count(a, mid+1, r);
    int i=l, j=mid+1, k=l;
    while (i<=mid && j<=r) {
        if (a[i] <= a[j]) save[k++] = a[i++];
        else { ans += mid - i + 1; save[k++] = a[j++]; }
    }
    while (i<=mid) save[k++] = a[i++];
    while (j<=r) save[k++] = a[j++];
    for (i=l; i<=r; i++) a[i] = save[i];
    return ans;
}

bool judge() {
    ll inv = merge_count(a, 0, n*n*n-2); // 空格為 0，不參與逆序對
    if (n & 1) return (inv % 2 == 0);
    int z = v % n, y = (v/n) % n;
    ll bu = 2*n - 2 - z - y; // 空格到終點的曼哈頓距離 (Y+Z)
    return ((bu ^ inv) & 1) == 0;
}

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        int flag = 0;
        for (int k=0; k
本題展示了如何將經典二維拼圖奇偶性理論推廣到高維，核心在於分析各維度移動對排列奇偶性的影響。