八数码问题c

八数码问题是一个经典的搜索问题，可以使用广度优先搜索（BFS）或A*算法来解决。以下是一个使用BFS解决八数码问题的C++代码示例：

#include <bits/stdc++.h>
using namespace std;

const int N = 3;
const int M = 362880; // 9!
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

struct Node {
    int puzzle[N][N];
    int x, y;
    int dist;
    int path[M];
    int id() const {
        int res = 0, mul = 1;
        for (int i = 0; i < N * N; ++i) {
            int cnt = 0;
            for (int j = i + 1; j < N * N; ++j) {
                cnt += puzzle[j / N][j % N] < puzzle[i / N][i % N];
            }
            res += mul * cnt;
            mul *= N * N - i;
        }
        return res;
    }
    bool operator<(const Node& other) const {
        return dist + id() > other.dist + other.id();
    }
};

Node st, ed;
int fact[N * N], dist[M];

int bfs() {
    memset(dist, -1, sizeof(dist));
    queue<Node> q;
    st.dist = 0;
    q.push(st);
    while (!q.empty()) {
        Node t = q.front();
        q.pop();
        if (t.id() == ed.id()) {
            memcpy(ed.path, t.path, sizeof(int) * t.dist);
            return t.dist;
        }
        for (int i = 0; i < 4; ++i) {
            int nx = t.x + dx[i], ny = t.y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            Node u = t;
            swap(u.puzzle[nx][ny], u.puzzle[t.x][t.y]);
            u.x = nx, u.y = ny;
            u.dist = t.dist + 1;
            if (dist[u.id()] == -1) {
                dist[u.id()] = u.dist;
                u.path[u.dist] = i;
                q.push(u);
            }
        }
    }
    return -1;
}

int main() {
    fact[0] = 1;
    for (int i = 1; i < N * N; ++i) fact[i] = fact[i - 1] * i;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            scanf("%d", &st.puzzle[i][j]);
            if (st.puzzle[i][j] == 0) {
                st.x = i, st.y = j;
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            scanf("%d", &ed.puzzle[i][j]);
            if (ed.puzzle[i][j] == 0) {
                ed.x = i, ed.y = j;
            }
        }
    }
    int cnt = bfs();
    if (cnt == -1) {
        puts("impossible");
    } else {
        for (int i = 0; i < cnt; ++i) {
            printf("%c", "lrud"[ed.path[i]]);
        }
        puts("");
    }
    return 0;
}

这段代码中使用了结构体`Node`来表示状态节点，其中`puzzle[N][N]`表示八数码矩阵，`x`和`y`表示空格的位置，`dist`表示到起点的距离，`path[M]`表示路径。`id`函数用于计算状态的哈希值。运行时间为$O(N^2 \cdot N!)$。

需要注意的是，这段代码中使用了`bits/stdc++.h`头文件，这个头文件只在一些特定的编译器上才可以使用，如果无法使用该头文件，可以将其替换为具体需要的头文件。