用·C++编写一个用状态空间表示法解决八数码问题的代码

好的，我可以为您提供一个基于状态空间表示法解决八数码问题的C++代码实现，以下是代码：

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 4;
const int MAXS = 1e5;
const int INF = 0x3f3f3f3f;

struct Node {
    int x, y;
}pos[MAXN * MAXN + 1];

char mp[MAXN + 1][MAXN + 1];
int n = 3, m = 3;
int tx, ty, st, ed;
int id[MAXN + 1][MAXN + 1];
int fac[MAXN + 1] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320 };
int vis[MAXS], pre[MAXS], op[MAXS];

int get_hash(char* str) {
    int v = 0;
    for (int i = 0; i < n * m; i++) {
        int num = str[i] - '0';
        int cnt = 0;
        for (int j = i + 1; j < n * m; j++) {
            if (str[j] < str[i]) cnt++;
        }
        v += cnt * fac[n * m - i - 1];
    }
    return v;
}

bool check(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

void bfs() {
    queue<int> q;
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    memset(op, -1, sizeof(op));
    st = get_hash((char*)mp);
    ed = get_hash("123456780");
    q.push(st);
    vis[st] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        int x, y;
        for (int i = 0; i < n * m; i++) {
            if (u / fac[i] % 10 == 0) {
                x = pos[i + 1].x;
                y = pos[i + 1].y;
                break;
            }
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (check(nx, ny)) {
                int v = u;
                int p = id[x][y], np = id[nx][ny];
                int t = v / fac[p] % 10;
                v = v - t * fac[p] + t * fac[np];
                t = v / fac[np] % 10;
                v = v - t * fac[np] + t * fac[p];
                if (!vis[v]) {
                    vis[v] = 1;
                    pre[v] = u;
                    op[v] = i;
                    q.push(v);
                }
            }
        }
    }
}

void print(int u) {
    if (pre[u] == -1) return;
    print(pre[u]);
    printf("%c", dir[op[u]]);
}

int main() {
    // input
    for (int i = 0; i < n; i++) {
        scanf("%s", mp[i]);
        for (int j = 0; j < m; j++) {
            if (mp[i][j] == '0') {
                tx = i; ty = j;
            }
            else {
                id[i][j] = mp[i][j] - '0';
                pos[id[i][j]].x = i;
                pos[id[i][j]].y = j;
            }
        }
    }

    // bfs
    bfs();

    // output
    if (vis[ed]) print(ed);
    else printf("unsolvable");
    printf("\n");

    return 0;
}

这个代码实现了使用状态空间表示法求解八数码问题的过程。它的基本思路是：将每个状态看作一个节点，通过每次移动0（即空格）到相邻的格子，生成新的节点，不断扩展节点，直到找到目标状态为止。在这个过程中，需要使用哈希表来判断一个状态是否已经出现过，以避免重复扩展。