用c++语言写出八数码算法代码

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

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

const int MAXN = 3;
const int MAXS = 1e5 + 10;

struct Node {
    int a[MAXN][MAXN];
    int x, y, f, g, h;
    bool operator<(const Node& b) const {
        return f > b.f;
    }
    bool operator==(const Node& b) const {
        for (int i = 0; i < MAXN; i++) {
            for (int j = 0; j < MAXN; j++) {
                if (a[i][j] != b.a[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
};

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

Node start, target;
map<Node, int> vis;
priority_queue<Node> q;

int h(Node& u) {
    int res = 0;
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            if (u.a[i][j] == 0) {
                continue;
            }
            int x = (u.a[i][j] - 1) / MAXN;
            int y = (u.a[i][j] - 1) % MAXN;
            res += abs(i - x) + abs(j - y);
        }
    }
    return res;
}

void bfs() {
    start.g = 0;
    start.h = h(start);
    start.f = start.g + start.h;
    q.push(start);
    vis[start] = 1;
    while (!q.empty()) {
        Node u = q.top();
        q.pop();
        if (u == target) {
            cout << u.g << endl;
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = u.x + dx[i];
            int ny = u.y + dy[i];
            if (nx < 0 || nx >= MAXN || ny < 0 || ny >= MAXN) {
                continue;
            }
            Node v = u;
            swap(v.a[u.x][u.y], v.a[nx][ny]);
            v.x = nx;
            v.y = ny;
            v.g = u.g + 1;
            v.h = h(v);
            v.f = v.g + v.h;
            if (vis[v]) {
                continue;
            }
            vis[v] = 1;
            q.push(v);
        }
    }
}

int main() {
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            cin >> start.a[i][j];
            if (start.a[i][j] == 0) {
                start.x = i;
                start.y = j;
            }
        }
    }
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            target.a[i][j] = i * MAXN + j + 1;
            if (target.a[i][j] == MAXN * MAXN) {
                target.a[i][j] = 0;
            }
        }
    }
    bfs();
    return 0;
}

在这里，我们使用了一个结构体Node来表示八数码问题中的一个状态，其中a数组存储了每个格子的数字，x和y存储了空格的位置，f、g和h分别表示当前状态的估价函数值、从初始状态到当前状态的代价和和从当前状态到目标状态的估计代价。

我们还使用了一个优先队列q来存储当前状态，使用一个map来记录每个状态是否已经被访问，避免重复访问。在bfs函数中，我们使用A*算法计算每个状态的估价函数，并将其插入优先队列中。每次取出估价函数值最小的状态进行拓展，直到找到目标状态为止。