python/TangDou/AcWing/IDAstar/180_AStar.cpp

#include <cstdio>
#include <cstring>
#include <unordered_set>
#include <queue>
#include <algorithm>

using namespace std;
typedef unsigned long long ULL; //自动溢出的ULL，计算整数数组的HASH值
const int B = 17;               // 17进制，用于HASH计算，这是大于15的第一个质数
const int N = 15;
int n;
unordered_set<ULL> b; //用于检测一个状态是否已经访问过了

struct Node {
    int v[N]; //当前的状态
    int step; //步数
    int f;    //估值
    bool operator<(const Node &x) const { //重载小于号
        return x.f < f;
    }
} x;

//优先队列
priority_queue<Node> q;

//检测是否到了目标状态
bool check(Node x) {
    for (int i = 0; i < n; i++)
        if (x.v[i] != i + 1) return false;
    return true;
}

// 计算数组状态的hash值
ULL getHash(Node x) {
    ULL res = 0;
    for (int i = 0; i < n; i++) res = res * B + x.v[i];
    return res;
}

//估值函数，1次变更，可以最多修改3个后继，现在有res个后继，最少的修改次数是 ⌊res/3⌋=(res+3-1)/3
int f(Node x) {
    int res = 0;
    for (int i = 1; i < n; i++)
        if (x.v[i] != x.v[i - 1] + 1) res++;
    return (res + 2) / 3;
}

// AStar
int bfs() {
    while (q.size()) {
        Node u = q.top(); //取出当前状态
        q.pop();

        if (u.f >= 5) return 5;      //当前状态无法在5步之内到达终点，返回无结果
        if (check(u)) return u.step; //如果第一次获取到了一个成功的状态，返回当前步数

        for (int len = 1; len < n; len++) { //枚举长度
            for (int st = 0; st + len - 1 < n; st++) { //枚举起始坐标
                for (int ed = st + len; ed < n; ed++) {
                    //抄出来
                    memcpy(x.v, u.v, sizeof u.v);

                    //三次翻转，子串对调
                    reverse(x.v + st, x.v + st + len);
                    reverse(x.v + st + len, x.v + ed + 1);
                    reverse(x.v + st, x.v + ed + 1);

                    //如果此状态已经进过优先队列，那么放弃掉
                    ULL hash = getHash(x);
                    if (b.count(hash)) continue;
                    //记录使用过
                    b.insert(hash);

                    //修改步数
                    x.step = u.step + 1;
                    //计算h值 h = g + f
                    x.f = x.step + f(x);
                    //入队列
                    q.push(x);
                }
            }
        }
    }
    return 5;
}

// AC 279 ms
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        //清空Hash表
        b.clear();
        //清空优先队列,清空优先队列的一个小技巧
        q = {};

        scanf("%d", &n);

        //初始状态入队列
        for (int i = 0; i < n; i++) scanf("%d", &x.v[i]); //当前的数组状态
        x.step = 0;                                       //原始状态，步数为0
        x.f = f(x);                                       //到达终点的最少步数估值

        q.push(x);            //对象入队列
        b.insert(getHash(x)); //记录此状态已使用

        int res = bfs(); // A*寻路

        if (res >= 5)
            puts("5 or more");
        else
            printf("%d\n", res);
    }
    return 0;
}