生成A*算法求解八数码问题，使用“与目标棋局相比，位置不符的数码数目”的启发函数的C++代码

以下是使用A*算法求解八数码问题的C++代码，其中启发函数使用“与目标棋局相比，位置不符的数码数目”：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int maxn = 1000 + 5;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

int a[3][3], goal[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};
int f[maxn], g[maxn], h[maxn], fa[maxn], vis[maxn], d[maxn];
int n = 0;

struct node {
    int a[3][3], x, y, step;
    int get_h() {
        int ans = 0;
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                if(a[i][j] == 0) continue;
                if(a[i][j] != goal[i][j]) ans++;
            }
        }
        return ans;
    }
    bool operator < (const node &rhs) const {
        return step + h[n] > rhs.step + h[n];
    }
};

node make_node(int x, int y, int step, int fa) {
    node tmp;
    tmp.x = x, tmp.y = y, tmp.step = step, tmp.a[x][y] = a[x][y], tmp.a[x ^ 1][y] = a[x ^ 1][y], tmp.a[x][y ^ 1] = a[x][y ^ 1], tmp.a[x ^ 1][y ^ 1] = a[x ^ 1][y ^ 1];
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            if(i == x && j == y) continue;
            if(i == x ^ 1 && j == y ^ 1) continue;
            if(i == x && j == y ^ 1) continue;
            if(i == x ^ 1 && j == y) continue;
            tmp.a[i][j] = a[i][j];
        }
    }
    f[++n] = step + h[n], g[n] = step, fa[n] = fa;
    for(int i = 0; i < n - 1; i++) {
        if(!memcmp(&tmp, &d[i], sizeof(tmp))) {
            n--;
            return d[i];
        }
    }
    return tmp;
}

void output(int x) {
    if(!x) return;
    output(fa[x]);
    printf("(%d, %d)\n", d[x].x, d[x].y);
}

int main() {
    priority_queue<node> q;
    node start;
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            scanf("%d", &a[i][j]);
            if(a[i][j] == 0) {
                start.x = i, start.y = j;
            }
        }
    }
    start.step = 0;
    memcpy(start.a, a, sizeof(a));
    q.push(start);
    memset(vis, 0, sizeof(vis));
    h[0] = start.get_h();
    d[0] = start;
    vis[start.x * 3 + start.y] = 1;
    while(!q.empty()) {
        node u = q.top();
        q.pop();
        if(!u.get_h()) {
            output(n);
            return 0;
        }
        for(int i = 0; i < 4; i++) {
            int nx = u.x + dx[i], ny = u.y + dy[i];
            if(nx < 0 || nx > 2 || ny < 0 || ny > 2) continue;
            node v = make_node(nx, ny, u.step + 1, n);
            if(vis[v.x * 3 + v.y]) continue;
            q.push(v);
            vis[v.x * 3 + v.y] = 1;
            d[n] = v;
        }
    }
    return 0;
}

这里使用了一个 `node` 结构体来表示每个状态，其中 `a` 数组表示当前状态的棋盘布局，`x` 和 `y` 表示空格的位置，`step` 表示当前状态的步数，`get_h` 函数用来计算当前状态和目标状态之间的启发函数值。在 `make_node` 函数中，使用了双向 BFS 的思想，从当前状态向周围四个状态转移，如果当前状态已经在前面出现过，则直接返回前面的状态。在主函数中，使用了优先队列来维护状态的搜索顺序，每次取出启发函数值最小的状态进行搜索。