【POJ2286】The Rotation Game

2015.08.03 09:14 Mon | 25次阅读 | 旧日oi | 固定链接 | 源码

题目大意

好长啊,自己看吧,别忘了解为0时要输出一串英文,并且要求字典序最小。

题解

IDA*搜索轻松水过。虽然丑了一点,但还是很清晰明了的……

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a[25],bound,ans,path[10005];
char op[8]={'A','B','C','D','G','H','E','F'};
int c[8]={7,8,9,12,13,16,17,18};
int w[8][7]=
{
    {1,3,7,12,16,21,23},
    {2,4,9,13,18,22,24},
    {11,10,9,8,7,6,5},
    {20,19,18,17,16,15,14},
    {14,15,16,17,18,19,20},
    {5,6,7,8,9,10,11},
    {24,22,18,13,9,4,2},
    {23,21,16,12,7,3,1}
}
int t[4];
int h()
{
    t[1]=t[2]=t[3]=0;
    for(int i=0;i<8;i++)
    t[a[c[i]]]++;
    return min(8-t[1],min(8-t[2],8-t[3]));
}
void change(int way)
{
    int t=a[w[way[0]]];
    for(int i=1;i<7;i++)
    a[w[way][i-1]]=a[w[way][i]];
    a[w[way][7]]=t;
}
int dfs(int d,int pre)
{
    int v=h();
    if(v+d>bound) return v+d;
    if(!v) 
    {
        ans=a[7];
        return d;
    }
    int nxt=0x3f3f3f3f;
    for(int i=0;i<8;i++)
    if(i+pre!=7)
    {
        path[d]=i;
        change(i);
        int k=dfs(d+1,i);
        if(ans) return k;
        nxt=min(nxt,k);
        change(7-i);
    }
    return nxt;
}
int main()
{
    while(cin>>a[1]&&a[1])
    {
        ans=0;
        for(int i=2;i<=24;i++) scanf("%d",&a[i]);
        bound=h();
        if(!bound) 
        {
            print("%d\n",a[7]);
            puts("No moves needed");
            continue;
        }  
        while(!ans) bound=dfs(0,-1);
        printf("%d\n",ans);
        for(int i=0;i<bound;i++) printf("%c",op[path[i]]);puts("");
    }
}```