宽度优先八数码c++

下面是一个基于宽度优先搜索算法实现的八数码问题解决程序的 C++ 代码：

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

// 八数码的状态结构体
struct node {
    int num[3][3]; // 表示八数码的矩阵
    int x, y;      // 空格的位置
    int step;      // 到达当前状态的步数
    int pre;       // 前驱状态的编号
} s, e, u, v;

int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320}; // 阶乘
int dx[] = {-1, 0, 1, 0}; // 上下左右移动
int dy[] = {0, 1, 0, -1};

int cantor(int a[]) { // 康拓展开
    int sum = 0;
    for (int i = 0; i < 9; i++) {
        int t = 0;
        for (int j = i + 1; j < 9; j++)
            if (a[i] > a[j])
                t++;
        sum += t * fac[9 - i - 1];
    }
    return sum;
}

void reverse_cantor(int x, int a[]) { // 康拓展开的逆运算
    int vis[10] = {0};
    for (int i = 0; i < 9; i++) {
        int t = x / fac[9 - i - 1];
        x %= fac[9 - i - 1];
        for (int j = 1; j <= 9; j++)
            if (!vis[j]) {
                if (t == 0) {
                    a[i] = j;
                    vis[j] = 1;
                    break;
                } else
                    t--;
            }
    }
}

int bfs() {
    queue<node> q;
    map<int, int> mp;
    s.step = 0;
    s.pre = -1;
    int a[10];
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            a[i * 3 + j] = s.num[i][j];
    mp[cantor(a)] = 1;
    q.push(s);
    while (!q.empty()) {
        u = q.front();
        q.pop();
        if (memcmp(u.num, e.num, sizeof(u.num)) == 0)
            return u.pre;
        for (int i = 0; i < 4; i++) {
            int nx = u.x + dx[i], ny = u.y + dy[i];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                memcpy(&v, &u, sizeof(u));
                swap(v.num[u.x][u.y], v.num[nx][ny]);
                v.x = nx, v.y = ny;
                v.step++;
                int a[10];
                for (int i = 0; i < 3; i++)
                    for (int j = 0; j < 3; j++)
                        a[i * 3 + j] = v.num[i][j];
                int code = cantor(a);
                if (!mp[code]) {
                    mp[code] = 1;
                    v.pre = mp.size() - 1;
                    q.push(v);
                }
            }
        }
    }
    return -1;
}

int main() {
    // 输入初始状态和目标状态
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) {
            cin >> s.num[i][j];
            if (s.num[i][j] == 0)
                s.x = i, s.y = j;
        }
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            cin >> e.num[i][j];
    int ans = bfs();
    if (ans == -1)
        cout << "无解" << endl;
    else {
        cout << "步数为：" << u.step << endl;
        int path[1000], cnt = 0;
        while (ans != -1) {
            path[cnt++] = u.pre;
            u = q[u.pre];
        }
        cout << "解路径为：";
        for (int i = cnt - 1; i >= 0; i--)
            cout << " " << path[i];
        cout << endl;
    }
    return 0;
}

其中，`cantor` 函数实现康拓展开，用于将每个状态映射到一个唯一的整数上；`reverse_cantor` 函数实现康拓展开的逆运算，用于从一个整数反推出对应的状态；`bfs` 函数实现基于宽度优先搜索算法的八数码问题的解决。程序的输入为两个 $3\times3$ 的矩阵，分别表示初始状态和目标状态，输出为最少需要多少步才能从初始状态到达目标状态，以及从初始状态到达目标状态的解路径。