$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

笔记：

这题是$BFS$的一个拓展练习。
我们把一个$3 \times 3$的矩阵压缩到一个$string$里。
例如：

a b c
d e f
g h i

压缩为：abcdefghi。
对于每一状态我们尝试把空格（$x$）上下左右移动，直到搜索到答案12345678x。

代码：

#include<bits/stdc++.h>
using namespace std;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
queue<string> q;
unordered_map<string, int> d;
int ds, k, px, py;
int bfs(string x) {
    q.push(x);
    d[x] = 0;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        ds = d[t];
        if (t == "12345678x") return ds;
        k = t.find('x');
        px = k / 3, py = k % 3;
        for (int i = 0; i < 4; i ++ ) {
            int a = px + dx[i], b = py + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3) {
                swap(t[k], t[a * 3 + b]);
                if (! d.count(t)) d[t] = ds + 1, q.push(t);
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    return -1;
}
int main() {
    string a, b;
    for (int i = 0; i <9; i ++ ) cin >> b, a += b;
    cout << bfs(a);
}