八数码问题a*算法c++

以下是使用C++实现八数码问题A*算法的代码：

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

const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int n, m, ans;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1 -1, 0, 0};
int a[3][3], b[3][3], vis[MAXN], f[MAXN], g[MAXN], h[MAXN], pre[MAXN];

struct node {
    int x, y, step, id;
    bool operator < (const node &rhs) const {
        return step + h[id] > rhs.step + h[rhs.id];
    }
};

int get_id(int a[][3]) {
    int res = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            res = res * 10 + a[i][j];
        }
    }
    return res;
}

void get_pos(int id, int a[][3]) {
    for (int i = 2; i >= 0; i--) {
        for (int j = 2; j >= 0; j--) {
            a[i][j] = id % 10;
            id /= 10;
            if (a[i][j] == 0) {
                n = i, m = j;
            }
        }
    }
}

int calc_h(int a[][3]) {
    int res = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (a[i][j] == 0) continue;
            int x = (a[i][j] - 1) / 3, y = (a[i][j] - 1) % 3;
            res += abs(x - i) + abs(y - j);
        }
    }
    return res;
}

void print(int id) {
    if (pre[id] == -1) return;
    print(pre[id]);
    int a[3][3];
    get_pos(id, a);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void A_star() {
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    memset(f, 0x3f, sizeof(f));
    memset(g, 0x3f, sizeof(g));
    priority_queue<node> q;
    int id = get_id(a);
    f[id] = g[id] = 0;
    h[id] = calc_h(a);
    q.push((node){n, m, 0, id});
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        if (vis[u.id]) continue;
        vis[u.id] = 1;
        if (u.id == get_id(b)) {
            ans = u.step;
            return;
        }
        int x = u.x, y = u.y;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
            swap(a[x][y], a[nx][ny]);
            int id = get_id(a);
            if (!vis[id] && u.step + 1 + calc_h(a) < f[id]) {
                f[id] = u.step + 1 + calc_h(a);
                g[id] = u.step + 1;
                pre[id] = u.id;
                q.push((node){nx, ny, u.step + 1, id});
            }
            swap(a[x][y], a[nx][ny]);
        }
    }
}

int main() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            scanf("%d", &b[i][j]);
        }
    }
    A_star();
    printf("%d\n", ans);
    print(get_id(b));
    return 0;
}