题解 UVA1343 旋转游戏 The Rotation Game

· · 题解

IDA* 算法

IDA（带有估价函数的迭代加深） = ID(迭代加深dfs）+ A(估价函数）

听起来很高大上是吗?

其实很简单，咱们一个一个说。

所谓迭代加深，顾名思义，就是不断加深搜索深度。

在 dfs 的过程中会形成一颗搜索树，dfs 的特点就是找到一个子树就硬着头皮往下拱，不管拱到多深，这样的时间复杂度很容易炸。

有些题目中，我们能看出答案在搜索树中非常浅的位置，这样的话就可以从小到大限制搜索深度。

什么意思？

就是先假设最大深度为1，如果没搜到再设为2重新搜……以此类推

显然，会有一部分被重复遍历，但这点重复遍历与任凭其深度增大相比还是微不足道滴~

估价函数就是在迭代加深的基础上，我们估算一下最好情况下还需要走几步，如果当前步数+最好情况步数还超过限制，那就提前回溯。

对应到这道题，我们不断限制操作的步数进行迭代加深，并加入一个剪枝：减掉互逆操作（显然互逆操作没有意义……）

估价函数：最好情况下，每操作一次中间就能多一个我们想要的数，因此估价函数 = 8 - 中间最多的数的个数

注意实现的细节，具体看代码吧。

Code：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

//输入的时候给每个位置都标上号 

const int opt[8][7]=//每一步操作拉动了那些点
{
    {22,20,15,11,6,2,0},
    {23,21,17,12,8,3,1},
    {4,5,6,7,8,9,10},
    {13,14,15,16,17,18,19},
    {1,3,8,12,17,21,23},
    {0,2,6,11,15,20,22},
    {19,18,17,16,15,14,13},
    {10,9,8,7,6,5,4}
};
const int oppo[8]={5,4,7,6,1,0,3,2};//逆操作（剪枝用） 
const int cen[8]={6,7,8,11,12,15,16,17};//中间的点 

int mp[24],ans[10005];//ans记录答案 
bool flag;//游戏结束标记 

inline int f()//估价函数 
{
    int tot[4]={0},res=8;
    for(int i=0;i<8;i++) tot[mp[cen[i]]]++;
    for(int i=1;i<=3;i++){
        res=min(res,8-tot[i]);
    }
    return res;
}

inline void dfs(int x,int dep,int last)
{
    if(flag) return ;
    if(x-1+f()>dep) return ;
    if(x>dep){
        if(!f()){
            flag=true;
            for(int i=1;i<=dep;i++){
                cout<<(char)(ans[i]+'A');
            }
            cout<<endl;
            cout<<mp[6]<<endl;
        }
        return ;
    }
    for(int i=0;i<8;i++){
        if(last!=-1&&i==oppo[last]) continue;//互逆操作 
        int raw=mp[opt[i][6]];
        for(int j=6;j>=1;j--){
            mp[opt[i][j]]=mp[opt[i][j-1]]; 
        }
        mp[opt[i][0]]=raw;//旋转
        ans[x]=i;
        dfs(x+1,dep,i);
        raw=mp[opt[i][0]];
        for(int j=0;j<6;j++){
            mp[opt[i][j]]=mp[opt[i][j+1]];
        }
        mp[opt[i][6]]=raw;//回溯，再倒着转回去 
    }
}

int main()
{
    while(cin>>mp[0]){
        if(!mp[0]) return 0;
        flag=false;
        for(int i=1;i<=23;i++){
            cin>>mp[i];
        }
        if(!f()){
            puts("No moves needed");
            cout<<mp[6]<<endl;
            continue;
        }
        for(int i=1;i<=100000;i++){
            dfs(1,i,-1);
            if(flag) break;
        }
    }
    return 0;
}