#include<bits/stdc++.h> usingnamespace std; constint M = 8, N = 10, INF = 0x3f3f3f3f; constint dx[] = {0, 1, 0, -1}; constint dy[] = {1, 0, -1, 0}; intManhattan_distance(int ax, int ay); voidprint(); structpoint { int x, y; int dist, cost; // 到终点的距离 从起点到目前的距离 int f = dist; // 评估函数
point() {} point(int x, int y, int cost) : x(x), y(y), dist(Manhattan_distance(x, y)), cost(cost) {} booloperator>(const point &rhs) const// 运算符重载,根据 f 比较大小 { return f > rhs.f; }
structNode { int board[N][N]; // 0-8 int x, y; // 0的位置 int g, h; // g为当前步数,h为估价函数 int Cantor; // Cantor展开
// 重载运算符,用于优先队列 booloperator<(const Node &a) const { return g + h < a.g + a.h; } };
structPath { int pre; // 前驱节点 int dir; // 前驱节点到当前节点的移动方向 } path[MAX];
bool vis[MAX];
inlinevoidswapNode(Node &a, Node &b) { Node t = a; a = b; b = t; }
inlinevoidswap(int &a, int &b) { int t = a; a = b; b = t; }
inlineintabs(int x) { return x > 0 ? x : -x; }
// 手写优先队列 structPriorityQueue { Node q[MAX]; int size;
PriorityQueue() { size = 0; }
voidpush(Node x) { q[++size] = x; int i = size; while (i > 1 && q[i] < q[i / 2]) { swapNode(q[i], q[i / 2]); i /= 2; } }
voidpop() { q[1] = q[size--]; int i = 1; while (i * 2 <= size) { int t = i; if (q[i * 2] < q[t]) t = i * 2; if (i * 2 + 1 <= size && q[i * 2 + 1] < q[t]) t = i * 2 + 1; if (t == i) break; swapNode(q[i], q[t]); i = t; } }
Node top() { return q[1]; }
boolempty() { return size == 0; }
voidclear() { size = 0; } } q;
inlineintgetCantor(Node e) {
int a[9], k = 0;
for (int i = 0; i < N; i++) //将数据排成一排,便于计算 { for (int j = 0; j < N; j++) a[k++] = e.board[i][j]; }
int x = 0; for (int i = 0; i < 9; i++) { int count = 0; for (int j = i + 1; j < 9; j++) { if (a[i] > a[j]) count++; } x += FACT[9 - i - 1] * count; } return x; }
inlineintgetH(Node e) { int res = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (e.board[i][j] == 0) continue; int x = (e.board[i][j] - 1) / N; int y = (e.board[i][j] - 1) % N; res += abs(x - i) + abs(y - j); } } return res; }