例 7-10 uva12212（迭代加深搜索）

题意：对于一段数字，每次可以剪切一段连续的自然数，粘贴到任意部分，使其变成升序

思路：

考虑的是进行搜索，深搜并不能保证是最短，广搜感觉每层的情况太多。

迭代加深：枚举搜索深度，然后进行深搜。

这种方法比较适用于不知道明显深度的，以及每层展开情况过多而导致bfs不行的。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
typedef long long ll;
using namespace std;


int maxd;
int n;
struct node
{
    int matrix[12];
};

int get_h(node t)             //可能进行的最大深度
{
    int num = 0,i;
    for(i = 1; i < n; i++)
        if(t.matrix[i] + 1 != t.matrix[i+1])
            num ++;
    if(t.matrix[i] != n)
        num++;
    return num;
}

node change(int from,int to,int x,node t)   //利用数组替代指针
{
    int tot;
    int next[20],tmp[20];
    for(int i=0; i <= n; i++)
        tmp[i]=t.matrix[i],next[i]=i+1;
    next[from-1]=to+1;
    next[x]=from;
    next[to]=x+1;
    for(int i=next[0],tot=1; tot<=n; i=next[i],tot++)
    {
        t.matrix[tot]=tmp[i];
    }
    return t;
}



bool dfs(node cur,int tt)
{
    int h = get_h(cur);
    int flag = 1;
    for(int i = 1; i <= n; i++)
    {
        if(cur.matrix[i] != i);
        {
            flag = 0;
            break;
        }
    }
    if(flag )
        return true;
    if(tt == maxd)
        return h == 0;
    if(tt*3+h > maxd*3)
        return false;
    for(int from = 1; from <= n; from++)
        for(int to = from; to <= n; to++)
            for(int i = 0; i <= n; i++)
            {
                node tp;
                memcpy(tp.matrix,cur.matrix,sizeof(int)*(n+1));
                if(i >= from-1 && i <= to)
                        continue;
                tp = change(from,to,i,tp);
                if(dfs(tp,tt+1))
                    return true;
            }
    return false;
}

char ch;
int main()
{
    int cas = 1;
    while(scanf("%d",&n) && n)
    {
        node from;
        for(int i = 1; i <= n; i++)
            scanf("%d",&from.matrix[i]);
        for(maxd = 0;; maxd++)             //搜索深度
        {
            if(dfs(from,0))
                break;
        }
        printf("Case %d: %d
",cas++,maxd);
    }
    return 0;
}

例 7-10 uva12212（迭代加深搜索）

相关推荐