程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 4801 Pocket Cube 四面魔方，模擬+搜索

hdu 4801 Pocket Cube 四面魔方，模擬+搜索

編輯：C++入門知識

魔方只有4面，且深度只有7層，所以可以搜索解決。由於模擬過程復雜，干脆用一個輔助數組記錄每次轉動每個點的對應位置，在腦中空間想象一下就好了。

值得注意的一點是不需要模擬12次（6條邊，順+逆2次）因為一條邊順時針就相當於另一條邊逆時針，所以只需要6次就好。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
using namespace std;
int ans;
int n;
int a[24];
void debug()
{
    printf("      %3d%3d\n",a[0],a[1]);
    printf("      %3d%3d\n",a[2],a[3]);
    for(int i=4;i<=9;i++) printf("%3d",a[i]);
    puts("");
    for(int i=10;i<=15;i++) printf("%3d",a[i]);
    puts("");
    for(int j=0;j<=3;j++)
    printf("      %3d%3d\n",a[16+j*2],a[16+j*2+1]);
    puts("---------------");
}
int h[10][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;
}