学步园

给定一个由连续整数组成的序列（长度1-9），问最少需要多少次剪切粘贴操作能变成1-n的连续序列

书中给的点拨非常重要：

1、启发函数的选择

2、迭代加深的应用

3、依据“每次剪切粘贴最多只能改变三个数字的位置正确性”来剪枝

另外有几个地方有疑惑：

1、剪切粘贴的操作，我尝试用memcpy替代中间数组，速度却更慢了

2、尝试用memcmp来判断到达目标，没有成功

3、如果不用map来做距离数组，如何用其他方法做呢？

Run Time: 3.219s

#include<cstring>
#include<cstdlib>
#include<cstdio>

#include<vector>
#include<map>
#include<queue>

using namespace std;

//Global Variables.
int kase = 1, n, maxd = 9;
vector<int> seq;
map<vector<int>,int> vis;
/////

int h(const vector<int>& a) {       //Heuristic Func
    int cnt = 0;
    for(int i = 1; i < a.size(); i ++) if(a[i] != a[i-1] + 1) cnt ++;
    return cnt;
}

struct State {
    vector<int> seq;
    int d, h;
    bool operator < (const State& s) const {
        return d + h > s.d + s.h;       //A* algorithm
    }
};

int solve() {
    priority_queue<State> q;
    State startS;
    startS.seq = seq;
    startS.d = 0;
    startS.h = h(startS.seq);
    q.push(startS);

    while(!q.empty()) {
        State u = q.top(); q.pop();

        if(vis.count(u.seq)) {
            if(vis[u.seq] > u.d) vis[u.seq] = u.d;
            else continue;
        } else vis[u.seq] = u.d;

        int flag = 1;
        for(int i = 0; i < n; i ++) if(u.seq[i] != (i+1)) { flag = 0; break; }  //Compare with target
        if(flag) {  //arrival.
            printf("Case %d: %d\n", kase ++, u.d);        //print ans
            return 1;
        }

        if(u.d > maxd) continue;        //Iterative Deepening
        if(3*u.d + h(u.seq) > 3*maxd) continue; //Pruning

        for(int a = 0; a < n; a ++) {
            for(int b = a; b < n; b ++) {       //cut start & end position
                for(int c = 0; c <= n; c ++) {   //paste position
                    vector<int> v = u.seq;
                    vector<int> tmp;
                    if(c < a) {
                        for(int i = a; i <= b; i ++) tmp.push_back(v[i]);
                        for(int i = c; i < a; i ++) tmp.push_back(v[i]);
                        for(int i = c; i <= b; i ++) v[i] = tmp[i-c];
                    }
                    else if(c > b) {
                        for(int i = b+1; i < c; i ++) tmp.push_back(v[i]);
                        for(int i = a; i <= b; i ++) tmp.push_back(v[i]);
                        for(int i = a; i < c; i ++) v[i] = tmp[i-a];
                    }
                    else continue;      //invalid operation.

                    State newS;
                    newS.seq = v;
                    newS.d = u.d + 1;
                    newS.h = h(newS.seq);
                    q.push(newS);
                }
            }
        }
    }
    return 0;
}

int main() {
    while(scanf("%d", &n) && n) {
        seq.resize(n);
        for(int i = 0; i < n; i ++) scanf("%d", &seq[i]);
        for(maxd = 1; maxd <= 9; maxd ++) {         //Iterative Deepening
            vis.clear();
            if(solve()) break;
        }
    }
    return 0;
}