八数码BFS

#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <queue>

using namespace std;

queue<string> q;
unordered_map<string, int> d;// 2、每种状态的距离，本题交换次数即为距离

int bfs(string state) {
    string target = "12345678x";
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

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

    // 1、队列不空时BFS
    while(q.size()) {    
        string t = q.front();
        q.pop();

        if(t == target) return d[t];

        int pos = t.find('x');
        int x = pos / 3, y = pos % 3;
        int distance = d[t];// 到当前状态已走过的距离

        // 尝试往下一个状态走
        for(int i = 0; i < 4; ++i) {
            int a = x + dx[i], b = y + dy[i];

            // 如果是合法的状态
            if(a >= 0 && a < 3 && b >= 0 && b < 3) {
                swap(t[pos], t[a * 3 + b]);
                // 若没访问过该种状态
                if(!d.count(t)) {
                    d[t] = distance + 1;
                    q.push(t);
                }
                // 还原以便寻找剩余可能的下一个状态
                swap(t[pos], t[a * 3 + b]);
            }
        }
    }

    return -1;
}

int main()
{
    string state;
    int n = 9;

    while(n--) {
        char tmp[2];
        cin >> tmp;

        state = state + tmp[0];
    }

    cout << bfs(state) << endl;

    return 0;
}