广度搜索实现八数码c++

好，下面是使用广度优先搜索算法实现八数码问题的 C++ 代码：

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

const int N = 3;  // 8数码问题的规模为3
const int dx[] = {0, 0, 1, -1};  // 四个方向的x坐标变化
const int dy[] = {1, -1, 0, 0};  // 四个方向的y坐标变化

struct Node {
    int state[N][N];  // 当前状态
    int x, y;  // 空格的位置
    int step;  // 当前步数
    Node() {}
    Node(int s[][N], int _x, int _y, int _step) {
        memcpy(state, s, sizeof(state));
        x = _x, y = _y, step = _step;
    }
};

int st[N][N];  // 初始状态
int ed[N][N];  // 目标状态

int bfs() {
    queue<Node> q;
    unordered_set<string> vis;  // 判重
    q.push(Node(st, 0, 0, 0));
    vis.insert(string((char*)st, (char*)st + N * N));  // 将初始状态加入到visit中
    while (q.size()) {
        auto t = q.front();
        q.pop();
        if (!memcmp(t.state, ed, sizeof(ed))) return t.step;  // 判断是否到达目标状态
        for (int i = 0; i < 4; i ++ ) {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= N || b < 0 || b >= N) continue;  // 判断是否越界
            auto c = t.state;
            swap(c[t.x][t.y], c[a][b]);  // 交换空格和相邻位置的数
            if (vis.count(string((char*)c, (char*)c + N * N))) continue;  // 判断是否重复
            q.push(Node(c, a, b, t.step + 1));  // 将新状态加入队列
        }
    }
    return -1;
}

int main() {
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            cin >> st[i][j];
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            cin >> ed[i][j];
    cout << bfs() << endl;
    return 0;
}

在该代码中，我们定义了一个 `Node` 结构体，表示当前状态，包含当前状态的数组 `state`，空格的位置 `x` 和 `y`，以及当前的步数 `step`。`bfs` 函数中使用队列进行广度优先搜索，搜索过程中使用哈希表进行判重。在搜索过程中，我们在四个方向上进行移动，并判断是否越界、是否重复，如果满足条件，我们将新状态加入队列。最终，如果到达目标状态，我们返回当前步数，否则返回 -1。

注意：上述代码只是给出了一种实现方法，实际上八数码问题还有其他解法和优化。