八数码

思路分析

本题是抽象化的$bfs$，看到最短路时可以联想到$bfs$，因为每一个状态变化到另一个状态都是一步，所以这么做是合理的

状态表示

对于$3 * 3$的图，最简单的可以想到用邻接矩阵去存储，不过可以我们可以借助字符串存储

剩下还有一个属性最短步数，我们可以用$pair$在队元素中存储，配合$set$判重。也可以用$unordered$_$map$负责存储最少步数以及剪枝判重（y总代码用的思路）

字符串与二维数组的坐标映射

字符串中下标为$a$的数字对应在邻接矩阵里的坐标是$(a / 3, a$ % $3)$
邻接矩阵下标为$(a, b)$对应在字符串的下表是$(a * 3 + b)$

状态转移

首先我们要找到$x$，这里可以直接用字符串的$find$函数求，返回的就是$x$在字符串的下标位置

其次与上下左右交换，这里和走迷宫相似，采用偏移量，不过我们首先要将字符串下表映射到二维数组下标，用二维数组下标进行变换，在返回到字符串下标

剪枝

对于重复过的状态，我们不在进行第二次遍历（由$bfs$最短路性质得第一遍历一定是最短路径），我们可以用哈希表 $unordered$_$map$来存储每一个状态和到达他状态的最小步数（第一次到达的步数）

剩下的就是套用bfs框架就行了

代码

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

using namespace std;

int bfs(string state)
{
    queue<string> q;
    unordered_map<string, int> d;

    q.push(state);
    d[state] = 0; // 初始状态的步数为0

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 偏移量

    string end = "12345678x"; // 终止状态
    while (q.size())
    {
        auto t = q.front();
        q.pop();

        if (t == end) return d[t]; // 如果是答案则返回

        int distance = d[t]; // 后面要修改t，所以先保存的
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i ++ ) // 将x与上下左右交换
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3) // 如果合法
            {
                swap(t[a * 3 + b], t[k]); // 交换位置
                if (!d.count(t)) // 如果是新状态就入队继续拓展
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[a * 3 + b], t[k]); // 恢复现场
            }
        }
    }

    return -1; // 找不到返回-1
}

int main()
{
    char s[2];

    string state;
    for (int i = 0; i < 9; i ++ )
    {
        cin >> s;
        state += *s;
    }

    cout << bfs(state) << endl;

    return 0;
}