IDA*算法

重点也是在找估价函数
此题的估价函数为，找错误的后继，每次交换能修改3个后继，因此最多需要 (res/3)上取整次修改，就可以到达最终状态
因此，判断当前depth+f()若>最大迭代次数，即可舍弃该分支

#include <iostream>
#include <cstring>

using namespace std;

const int N=20;
int q[N],w[6][N];
int T,n;

//估价函数
int f()
{
    int res=0;
    for(int i=1;i<=n-1;i++)
    {
        if(q[i+1]!=q[i]+1)
        res++;
    }
    return (res+2)/3;
}

int dfs(int depth,int max_depth)
{
    if(depth+f()>max_depth) return 0;
    //一定要有一个成功条件和失败条件
    //每次dfs前，先检查这个成功条件，用上一层更新好的q来检查
    if(f()==0) return 1;

    for(int len=1;len<=n;len++)
    {
        for(int l=1;l<=n-len+1;l++)
        {
            int r=l+len-1;
            //枚举把l~r的书放在哪个书的后面
            for(int k=r+1;k<=n;k++)
            {
                memcpy(w[depth],q,sizeof q);
                int y=l;
                for(int i=r+1;i<=k;i++,y++) q[y]=w[depth][i];
                for(int i=l;i<=r;i++,y++) q[y]=w[depth][i];
                if(dfs(depth+1, max_depth)==1) return 1;
                memcpy(q,w[depth],sizeof q);
            }
        }
    }
    return 0;
}

int main()
{
    cin>>T;
    while(T--)
    {
        memset(q,0,sizeof q);
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>q[i];
        }
        int depth=0;
        while(depth<5 && !dfs(0,depth)) depth++;

        if(depth>=5) cout<<"5 or more"<<endl;
        else cout<<depth<<endl;


    }
    return 0;
}