难点:

$\color{#AAF}{BFS四大核心:状态表示、状态转换、判重与信息记录、队列}$

1.BFS过程中，每个走到的点不是一个编号或元组，是一个状态(整张网格的分布)，可以用字符串存储多维数组信息

2.每个状态到起始状态之间的距离用哈希表unordered_map<string,int>存储

3.扩展节点的过程实际上是找每个状态能表示成哪些状态(空格x四周的点与空格x进行交换)；判断状态是否有效即判断状态是否在哈希表中出现过；每次向四周的点转换状态后要及时恢复，确保四周其他节点可以正确在当前队头状态基础上进行扩展

4.一维数组索引[k]映射到二维数组索引[x][y]

x = k / n，y = k % n，(n为一维数组的列数)

代码:

#include<bits/stdc++.h>
using namespace std;

int BFS(string state)
{
    string end = "12345678x";   // 终止状态
    queue<string> q;            // 队列 每个状态用一个字符串表示
    unordered_map<string,int> d;// 数组(计算距离 + 判重)

    q.push(state);
    d[state] = 0;
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        if(t == end) return d[t];
        int distance = d[t];
        int k = t.find('x');            // 找到空格x的位置
        int x = k / 3; int y = k % 3;   // 一维索引变二维索引
        int dx[] = {0,1,0,-1};int dy[] = {1,0,-1,0};    // 四周可以移动到空格处的点
        for(int i = 0;i < 4;i ++)
        {
            int xx = x + dx[i];int yy = y + dy[i];
            if(xx < 0 || xx >= 3 || yy < 0 || yy >= 3) continue;    // 越界
            swap(t[k],t[3 * xx + yy]);  // 状态转移
            if(!d.count(t))             // 判重 状态有效(之前未出现过)
            {
                d[t] = distance + 1;    // 更新距离
                q.push(t);              // 新状态入队
            }
            swap(t[k],t[3 * xx + yy]);  // 恢复状态 扩展周围其他节点
        }
    }
    return -1;                          // 不存在解决方案
}

int main()
{
    string state;
    for(int i = 0;i < 9;i ++)
    {
        char c;
        cin >> c;
        state += c;
    }
    cout << BFS(state);
    return 0;
}