题解 UVA1343 【旋转游戏】

从题意我们可以看到下图 建立map数组 把对应点的数组位置存下来

那么用IDA* 算法层次递进

不断的选择对象 然后用函数进行更改 赋予参数

具体见代码

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define LL long long
#define ULL unsigned long long
#define debug cout<<"bug"<<endl;
using namespace std;
inline void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    x=x*f; 
}
int map[25],depth,aim,CCC[4];
char ans[110];
inline int okk(int map[])//判断是否已经成功 
{
    int tmp=map[7];
    if(map[8]!=tmp||map[9]!=tmp||map[12]!=tmp||map[13]!=tmp||map[16]!=tmp||map[17]!=tmp||map[18]!=tmp)
       return 0;
    return 1;
}
inline int cc(int *g)//估价函数女 
{
    memset(CCC,0,sizeof CCC);
    CCC[g[7]]++,CCC[g[8]]++,CCC[g[9]]++,CCC[g[12]]++,CCC[g[13]]++,CCC[g[16]]++,CCC[g[17]]++,CCC[g[18]]++;
    return max(max(CCC[1],CCC[2]),CCC[3]);
}
void change(int *g,int a1,int a2,int a3,int a4,int a5,int a6,int a7)//移动函数 
{
    int tmp=g[a1];
    g[a1]=g[a2],g[a2]=g[a3],g[a3]=g[a4],g[a4]=g[a5],g[a5]=g[a6],g[a6]=g[a7],g[a7]=tmp;
}
inline int dfs(int g[],int dep,int before)
{
    if(depth-dep<8-cc(g)) return 0;//估价函数 
    if(dep>=depth) return 0;
    int tmp[25];
    for(int i=1;i<=8;i++)
    {   //剪枝 移过去的不移回来 
        if((i==1&&before==6)||(i==6&&before==1)) continue;
        if((i==2&&before==5)||(i==5&&before==2)) continue;
        if((i==3&&before==8)||(i==8&&before==3)) continue;
        if((i==4&&before==7)||(i==7&&before==4)) continue;

        for(int k=1;k<=24;k++) tmp[k]=g[k];
        switch(i)
        {
            case 1:ans[dep]='A';change(tmp,1,3,7,12,16,21,23);break;
            case 2:ans[dep]='B';change(tmp,2,4,9,13,18,22,24);break;
            case 3:ans[dep]='C';change(tmp,11,10,9,8,7,6,5);break;
            case 4:ans[dep]='D';change(tmp,20,19,18,17,16,15,14);break;
            case 5:ans[dep]='E';change(tmp,24,22,18,13,9,4,2);break;
            case 6:ans[dep]='F';change(tmp,23,21,16,12,7,3,1);break;
            case 7:ans[dep]='G';change(tmp,14,15,16,17,18,19,20);break;
            case 8:ans[dep]='H';change(tmp,5,6,7,8,9,10,11);break;
            default :cout<<"ERROR!"<<endl;
        }
        if(okk(tmp))
        {
            aim=tmp[7];
            ans[dep+1]='\0';
            return 1;
        }
        if(dfs(tmp,dep+1,i)) return 1;
    }
    return 0;
}
int main()
{
    while(1)
    {
        depth=0;
        read(map[1]); if(map[1]==0) break;
        for(int i=2;i<=24;i++) read(map[i]);
        if(okk(map))
        {
            printf("No moves needed\n");
            printf("%d\n",map[7]);
        }
        else
        {
            depth++;
            while(1)
            {
                if(dfs(map,0,-1))
                   break;
                depth++;
            }
            printf("%s\n",ans);
            printf("%d\n",aim);
        }
    }
    return 0;
}