$\Huge\color{orchid}{点击此处获取更多干货}$

BFS

之前提到过BFS很擅长处理“最少步数”问题，这次的八数码就是这样的问题
3行3列的矩阵可以按照需求文档中那样，去掉空格后按行优先存储为字符串，那么目标状态对应的字符串就是$\text{“12345678x”}$，其中x即为右下角的空格。然后，我们可以从需要被移动到右下角的空格x入手，依次搜索不同移动步数下，x的位置以及盘面的状态。既然转化为了x的移动，那么就可以使用BFS了。（这个问题还有个更高效的解决方法，在提高篇会介绍）

C++ 代码

#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;

//3阶的矩阵在问题中自动按行压缩存储

const string finish = "12345678x";//已确认目标状态
queue<string> q;
unordered_map<string,int> steps;//将每个状态对应的步数记录下来
int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

int main()
{
    string start;
    for (int i = 0; i < 9; i++) {
        char c;
        cin >> c;
        start += c;
    }
    q.push(start);
    steps[start] = 0;//起始状态步数默认0
    while (!q.empty()) {
        string cur = q.front();
        q.pop();
        int step = steps[cur];//需要事先记录，原因之后再说
        if (cur == finish) {    //已处于目标状态，输出步数
            cout << step << endl;
            return 0;
        }
        //在字符串中找到x的位置并转化为二维坐标
        int px = cur.find('x');
        int ox = px / 3, oy = px % 3;
        for (int i = 0; i < 4; i++) {
            int nx = ox + dx[i], ny = oy + dy[i];
            //判断新x的位置是否越界
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                //BFS搜索相邻状态时，是直接在当前状态的字符串上交换字符而得，此cur和前面的cur已经不同
                swap(cur[px],cur[3 * nx + ny]);
                if (!steps.count(cur)) {    //新状态添加进来，已有状态直接忽略
                    steps[cur] = step + 1;
                    q.push(cur);
                }
                //还原cur，进行下一次搜索
                swap(cur[px],cur[3 * nx + ny]);
            }
        }
    }
    cout << -1 << endl;
    return 0;
}