HDU 4801 Pocket Cube：四面魔方的模擬與搜索解法

題目背景

HDU 4801 Pocket Cube 是一道經典的魔方模擬與搜索題目。這個魔方只有 4 個面，且最大深度僅 7 層，因此可以通過深度優先搜索（DFS）來求解。關鍵在於如何高效地模擬魔方的旋轉操作。

核心思路

由於魔方旋轉的模擬過程較為複雜，採用一個輔助陣列 h[6][24] 預先記錄每種旋轉操作對 24 個角塊位置的映射關係。這樣在搜索時只需查表即可快速得到新狀態，避免了複雜的幾何計算。

優化：只需 6 種基本操作

魔方有 6 條邊，每條邊可順時針或逆時針旋轉，看似有 12 種操作。但實際上，一條邊的順時針旋轉等價於另一條邊的逆時針旋轉，因此只需定義 6 種基本旋轉操作即可覆蓋所有情況，大幅減少搜索分支。

算法流程

1. 讀取初始魔方狀態（24 個整數代表角塊顏色）。
2. 計算當前已完成的面數（cal() 函數）。
3. 使用 DFS 進行搜索，深度限制為給定的 n，並利用剪枝：若已達到最優解（6 面完成）或剩餘步數為 0 則返回。
4. 每次嘗試 6 種旋轉，應用映射表更新狀態，遞歸搜索，然後回溯恢復狀態。
5. 記錄搜索過程中出現的最大完成面數作為答案。

關鍵代碼片段

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;

int ans, n;
int a[24];

// 6 種基本旋轉的位置映射表
int h[6][24] = {
    {1,3,0,2,23,22,4,5,6,7,10,11,12,13,14,15,16,17,18,19,20,21,9,8},
    {2,0,3,1,6,7,8,9,23,22,10,11,12,13,14,15,16,17,18,19,20,21,5,4},
    {0,1,8,14,4,3,7,13,17,9,10,2,6,12,16,15,5,11,18,19,20,21,22,23},
    {0,1,11,5,4,16,12,6,2,9,10,17,13,7,3,15,14,8,18,19,20,21,22,23},
    {20,1,22,3,10,4,0,7,8,9,11,5,2,13,14,15,6,17,12,19,16,21,18,23},
    {6,1,12,3,5,11,16,7,8,9,4,10,18,13,14,15,20,17,22,19,0,21,2,23},
};

// 判斷四個位置顏色是否相同
int f(int x,int b,int c,int d) {
    return a[x]==a[b] && a[b]==a[c] && a[c]==a[d];
}

// 計算已完成的面數
int cal() {
    return f(0,1,2,3)+f(4,5,10,11)+f(6,7,12,13)+f(8,9,14,15)+f(16,17,18,19)+f(20,21,22,23);
}

void dfs(int last) {
    ans = max(ans, cal());
    if (ans == 6) return;
    if (!last) return;
    int tmp[24];
    memcpy(tmp, a, sizeof(a));
    for (int d = 0; d < 6; d++) {
        for (int i = 0; i < 24; i++) a[i] = tmp[h[d][i]];
        dfs(last - 1);
        memcpy(a, tmp, sizeof(tmp));
    }
}

int main() {
    while (~scanf("%d", &n)) {
        for (int i = 0; i < 24; i++) scanf("%d", &a[i]);
        ans = cal();
        dfs(n);
        printf("%d\n", ans);
    }
    return 0;
}

總結

本題通過預計算旋轉映射表，將複雜的空間幾何轉化為簡單的陣列查找，配合深度受限的 DFS 搜索，高效解決了四面魔方的最優解問題。這是一個典型的「狀態空間搜索 + 模擬優化」的範例。