c++实现： 利用A*算法实现八数码难题(九宫重排)的搜索。要求：输出每一步的状态，从控制端输入初始状态和目标状态

以下是使用C++实现A*算法解决八数码难题的示例代码。代码中包括了输入初始状态和目标状态、状态转换、A*算法搜索等功能。

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

const int maxn = 400000;
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };
const char op[] = { 'u','d','l','r' };

struct Node {
    int state[3][3];
    int f, g, h;
    int x, y;
    char path[maxn];
    bool operator < (const Node& rhs) const {
        return f > rhs.f;
    }
};

bool vis[maxn + 10];
Node node[maxn + 10];

int Hash(Node& u) {
    int res = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            res = res * 10 + u.state[i][j];
        }
    }
    return res % maxn;
}

void init() {
    memset(vis, false, sizeof(vis));
    memset(node, 0, sizeof(node));
}

void input(Node& u) {
    cout << "请输入初始状态：\n";
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> u.state[i][j];
            if (u.state[i][j] == 0) {
                u.x = i;
                u.y = j;
            }
        }
    }
    cout << "请输入目标状态：\n";
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            int t;
            cin >> t;
            node[maxn - 1].state[i][j] = t;
        }
    }
}

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

bool check(Node& u) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (u.state[i][j] != node[maxn - 1].state[i][j]) {
                return false;
            }
        }
    }
    return true;
}

void output(Node& u) {
    for (int i = 0; i < strlen(u.path); i++) {
        cout << u.path[i];
    }
    cout << endl;
}

void A_star(Node& start) {
    priority_queue<Node> q;
    start.g = 0;
    start.h = H(start);
    start.f = start.g + start.h;
    q.push(start);
    vis[Hash(start)] = true;
    while (!q.empty()) {
        Node u = q.top();
        q.pop();
        if (check(u)) {
            output(u);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = u.x + dx[i];
            int ny = u.y + dy[i];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                Node v = u;
                swap(v.state[v.x][v.y], v.state[nx][ny]);
                v.x = nx;
                v.y = ny;
                if (!vis[Hash(v)]) {
                    v.g++;
                    v.h = H(v);
                    v.f = v.g + v.h;
                    v.path[v.g - 1] = op[i];
                    vis[Hash(v)] = true;
                    q.push(v);
                }
            }
        }
    }
}

int main() {
    Node start;
    init();
    input(start);
    A_star(start);
    return 0;
}

在运行程序时，按照程序提示输入初始状态和目标状态即可。程序会输出每一步的状态，直到搜索到目标状态为止。