C++实现广度优先算法实现九宫重排

以下是C++实现广度优先算法实现九宫重排的示例代码：

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

// 目标状态
const vector<int> targetState = {1, 2, 3, 4, 5, 6, 7, 8, 0};

// 表示状态的结构体
struct State {
    vector<int> nums; // 状态数组
    int zeroIndex; // 0的位置
    int step; // 步数

    State() {}
    State(vector<int> nums, int zeroIndex, int step) :
        nums(nums), zeroIndex(zeroIndex), step(step) {}
};

// 广度优先搜索
int bfs(vector<int> startState) {
    queue<State> q; // 队列
    map<vector<int>, bool> visited; // 记录已访问过的状态
    State initState(startState, 0, 0); // 初始状态
    q.push(initState);
    visited[startState] = true;

    while (!q.empty()) {
        State curState = q.front();
        q.pop();
        if (curState.nums == targetState) { // 已找到目标状态
            return curState.step;
        }

        // 上下左右四个方向
        int dx[4] = {-1, 1, 0, 0};
        int dy[4] = {0, 0, -1, 1};
        for (int i = 0; i < 4; i++) {
            int x = curState.zeroIndex / 3 + dx[i];
            int y = curState.zeroIndex % 3 + dy[i];
            if (x >= 0 && x < 3 && y >= 0 && y < 3) { // 位置合法
                vector<int> newNums = curState.nums;
                swap(newNums[curState.zeroIndex], newNums[x * 3 + y]);
                if (!visited[newNums]) { // 新状态未曾访问过
                    State newState(newNums, x * 3 + y, curState.step + 1);
                    q.push(newState);
                    visited[newNums] = true;
                }
            }
        }
    }
    return -1; // 无法到达目标状态
}

int main() {
    vector<int> startState = {2, 8, 3, 1, 6, 4, 7, 0, 5};
    int step = bfs(startState);
    cout << step << endl; // 输出步数
    return 0;
}

其中，`State`结构体表示一个状态，包括`nums`表示状态数组，`zeroIndex`表示0的位置，`step`表示从初始状态到达该状态的步数。`bfs`函数实现广度优先搜索，`startState`为初始状态数组，返回从初始状态到目标状态需要的步数。在搜索过程中，使用队列`q`存储待搜索的状态，使用`visited`记录已访问过的状态，遇到新状态时将其加入队列中并标记为已访问。每次从队列中取出一个状态，遍历其上下左右四个方向，生成新状态，并判断该状态是否已访问过，若未访问过则将其加入队列中。最终，若搜索完所有状态仍未找到目标状态，则返回-1表示无法到达目标状态。