AcWing 845. 八数码

思路

1~8和x的每一种排列都是一个状态，通过移动x可以得到其他状态。

将每个状态当作一个点，每次移动当作一条权值为1的边。如果从状态A可以变换到状态B，则存在A到B的边。从 输入 变换到 正确排列 的过程就可以看作是从起点走到终点。这样，求最少变换次数就转换成求最短路的问题。

$BFS$第一次搜索到 正确排列 所需要的变换次数就是最少交换次数。在搜索过程中，需要记录每一个状态和相应的变换次数（即与起点的距离）。如果可以从 输入 变换到 正确序列，就输出最少交换次数；否则，就说明不能变换到 正确序列 ，也就是不存在最短路。

难点

1. 每个3×3的网格就是一个状态，状态怎样表示？ 将3×3的网格转换成长度为9的字符串，用字符串表示状态。
2. 与起点的距离该怎么记录？ 用哈希表记录。

$BFS$

1. 队列

queue<string> q;

1. 距离

unordered_map<string, int> d;

代码

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

int bfs(string start)
{
    string end="12345678x";//正确排列

    queue<string> q;
    unordered_map<string, int> d;

    q.push(start);/*初始状态入队*/
    d[start]=0;

    int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};//上、右、下、左四个方向的向量

    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, y=k%3;//求出x在3×3网格中的坐标（坐标从0开始）
        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)//未出界，x可以向该位置移动
            {
                swap(t[k], t[a*3+b]);//移动后的排列
                if(!d.count(t))//该排列未出现过
                {
                    d[t]=distance+1;
                    q.push(t);
                }
                swap(t[k], t[a*3+b]);//还原：由于原来的排列t没有备份，所以尝试下一个方向之前需要恢复原样
            }
        }
    }

    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;
}