bfs解八数码问题

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1};

// bfs宽搜对应的是一个图，搜索结果为一棵树
// bfs需要解决两个问题，一个是dist数组，一个是节点的状态表示和去重

int bfs(string start) { // 每一个状态都是一个图中的节点，这一点于前面的走迷宫不同
    // 在走迷宫中，每一个点都是一图中一个节点，这些节点本身并不会重复，每个节点到源点的距离与节点本身是映射好的
    // 而本题中的矩阵的状态是节点，因此为了不重复搜，需要哈希映射，同时映射每种状态对应的距离
    string end = "12345678x";
    queue<string> q;
    unordered_map<string, int> d;

    q.push(start);
    d[start] = 0;

    while (q.size()) {
        auto t = q.front();
        q.pop();

        int dis = d[t];
        int ind = t.find('x');
        int x = ind / 3, y = ind % 3;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx < 0 || yy < 0 || xx >= 3 || yy >= 3) continue;
            swap(t[xx * 3 + yy], t[ind]);  
            if (!d.count(t)) { // 没有重复搜索，是一个新的节点，则开始转移
                q.push(t);  // 节点入队列
                d[t] = dis + 1;  // 节点距离加1，放入map中
                if (t == end) return dis + 1;  // 判断当前节点是否是终点
            }
            swap(t[xx * 3 + yy], t[ind]);  // 回溯当之前到上一个节点
        }
    }
    return -1;
}

int main() {
    string start;
    for (int i = 0; i < 9; i++) {
        char c;
        cin >> c;
        start += c;
    }

    cout << bfs(start) << endl;

    return 0;
}