用C++广度优先实现经典八数码

好的，我可以帮你解答这个问题。

八数码问题是一种经典的搜索问题，可以使用广度优先搜索算法求解。以下是一个使用 C++ 实现的八数码问题求解程序示例：

#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>

using namespace std;

// 定义八数码状态结构体
struct State {
    int board[3][3]; // 八数码矩阵
    int x, y; // 空格位置
    int step; // 步数
    bool operator==(const State& other) const {
        return memcmp(board, other.board, sizeof(board)) == 0;
    }
};

// 定义哈希函数
namespace std {
template <>
struct hash<State> {
    size_t operator()(const State& s) const {
        size_t h = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                h = h * 10 + s.board[i][j];
            }
        }
        return h;
    }
};
}

// 判断是否为目标状态
bool isTargetState(const State& s) {
    return s.board[0][0] == 1 && s.board[0][1] == 2 && s.board[0][2] == 3 &&
           s.board[1][0] == 4 && s.board[1][1] == 5 && s.board[1][2] == 6 &&
           s.board[2][0] == 7 && s.board[2][1] == 8 && s.board[2][2] == 0;
}

// 判断是否越界
bool isValidPos(int x, int y) {
    return x >= 0 && x < 3 && y >= 0 && y < 3;
}

// 定义方向数组
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

// 求解八数码问题
int solve(State& start) {
    queue<State> q; // 搜索队列
    unordered_set<State> visited; // 哈希表，记录已访问的状态
    q.push(start);
    visited.insert(start);

    while (!q.empty()) {
        State cur = q.front();
        q.pop();

        if (isTargetState(cur)) {
            return cur.step;
        }

        // 枚举所有可能的下一步状态
        for (int i = 0; i < 4; i++) {
            int newx = cur.x + dx[i];
            int newy = cur.y + dy[i];
            if (isValidPos(newx, newy)) {
                State next = cur;
                swap(next.board[cur.x][cur.y], next.board[newx][newy]);
                next.x = newx;
                next.y = newy;
                next.step = cur.step + 1;
                if (visited.count(next) == 0) {
                    q.push(next);
                    visited.insert(next);
                }
            }
        }
    }

    return -1; // 无解
}

int main() {
    State start;
    cout << "请输入八数码矩阵（0 表示空格）：" << endl;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> start.board[i][j];
            if (start.board[i][j] == 0) {
                start.x = i;
                start.y = j;
            }
        }
    }
    start.step = 0;
    int steps = solve(start);
    if (steps == -1) {
        cout << "无解" << endl;
    } else {
        cout << "步数为：" << steps << endl;
    }
    return 0;
}

这个程序使用广度优先搜索算法求解八数码问题，其中定义了八数码状态结构体 `State`，哈希函数和判断是否为目标状态的函数 `isTargetState`。在 `solve` 函数中，我们使用队列 `q` 存储待搜索的状态，使用哈希表 `visited` 记录已经访问过的状态。我们不断从队列中取出状态，枚举所有可能的下一步状态，如果该状态未被访问过，则将其加入队列和哈希表。如果某个状态是目标状态，则返回该状态的步数，即为八数码问题的最少步数。如果搜索完所有状态仍未找到目标状态，则说明该问题无解。

你可以将八数码矩阵作为输入，运行这个程序，得到八数码问题的最少步数。