`bfs`中的八数码问题

例题

在一个 3×33×3 的网格中，1∼8 1∼8 这 88 个数字和一个 x 恰好不重不漏地分布在这 3×3 3×3 的网格中。

例如：

在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下:

现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

分析

看完了题目，这让我想起，我们之前可能玩过一种拼图的游戏，在玩游戏的过程中我们会得到一张比较好看的图片，但是它缺了一个口！然后呢，别人将这个图片给打乱了，就像9宫格这样打乱，让我们一个一个对着这个口移动回去。

在移动的过程中我们会发现，我们不是计算机，不可以很快的判断出我们要移动几步，因此我们会先按照我们的感觉，对x这个缺口的上下左右依次进行移动，看看移动之后是否会更快地把这个拼图给拼回去。但是我们在拼图的时候也可能会出现重复的情况，比如我们移动了若干步，最后我们还是回到了起点，这样的话，我们之前移动的那些步数不就直接没有用了吗？

所以，为了让我们的计算机不犯这种低级错误，我们得让我们的计算机知道我们之前走过哪些步骤，这就需要stl中的unordered_map来发挥作用了，我们可以把我们的状态用string类型的字符串来表示，int类型用来记录这种已经出现过的步数是什么时候走过的，同时为了管理我们的步数，我们还要添加一个stl中的queue容器来存储我们的步数

以下便是我们的初始状态

#include<iostream>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
const int N = 100010;

int main()
{
    string start;
    for (int i = 0; i < 9; i++)
    {
        char ch[2];
        cin >> ch;
        start += *ch;
    }
    cout << bfs(start) << endl;
}

我们用string类型的字符串数组来存储我们一开始的棋盘格局，例如string start = "123x46758",这样子也可以与我们的map保持一致，下面的for循环便是我们对初始状态的赋值

最后对于bfs(start)的返回值进行输出就得到结果啦！

bfs函数的算法设计

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

    string end = "12345678x";

上面的q,d是我们定义的两个stl容器，q.push(start)就是把我们的初始状态放到队列中，d[start]是用来记录这是我们第几步得到的结果，如上述的0就是我们的初始状态。

玩游戏时我们要一一试错，计算机是很蠢的，它也要一一试错，这时我们就要定义偏移量了，下面的dx,dy数组就是给我们调偏移量的，最后我们也要让电脑知道它有没有调错是吧，那我们还要设置一个string字符串end来记录结束标志，一旦我们找到了解那就直接结束了。

进入队列

while (q.size())
    {
        //入队
        auto t = q.front();
        q.pop();
        //如果t的状态与end状态一致，返回数值
        if (t == end) return d[t];
        int distance = d[t];
        //找到x的位置
        int k = t.find('x');
        //技巧:从一维数组转成二维将(k/竖直方向上的数)，(k%水平方向上的数)
        int x = k / 3, y = k % 3;
        //遍历每一处
        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[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;

首先，我们定义一个auto类型的变量t来更好地运用队列，引用队列中的第一个元素后，q.pop()把第一个元素出列，由于队列容器不支持我们拿出来它的中间值，所以我们这样做更加方便一些

每次我们先判断是否达到了预期效果，假如我们一开始就成功了，那就不用动图片任何一步就可以返回值了

我们在移动九宫格的时候是根据x的位置来进行移动的，同理，我们要让电脑找到我们x的位置在哪里，不然的话我们根本移动不了好吧，我们用k记录我们x的位置，用distance来记录当前步数所对应的值，比如在这个示例中，开始不是结束状态，我们不能一下子返回值，我们要拿一个distance来记录，由于我们一开始定义的string是一维数组的形式，这使得我们可以更好的找到x的位置

下面的方法就很有技巧性了，我们在一维数组中找到了x的位置，那怎么在二维数组上还原呢？有个技巧