845. 八数码(C++)

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

例如：

1 2 3
x 4 6
7 5 8

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

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

1 2 3
4 5 6
7 8 x

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

交换过程如下：

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x

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

输入格式

输入占一行，将 3×3 的初始网格描绘出来。

例如，如果初始网格如下所示：

1 2 3 
x 4 6 
7 5 8 

则输入为：1 2 3 x 4 6 7 5 8

输出格式

输出占一行，包含一个整数，表示最少交换次数。

如果不存在解决方案，则输出 −1。

输入样例：

2 3 4 1 5 x 7 6 8

输出样例

19

算法思路：

1. 状态表示： 将每个状态表示为一个长度为 9 的字符串，其中 'x' 表示空格位置。这样的状态空间是有限的，因为总共有 9 个位置，每个位置可以是 1~8 中的一个数字或者 'x'。

2. 广度优先搜索（BFS）： 从初始状态开始，使用 BFS 算法遍历状态空间。每次将当前状态出队，然后尝试将 'x' 分别与上、下、左、右四个方向的数字交换，生成新的状态。如果新状态是首次遇到的状态，则将其加入队列，并记录当前步数。

3. 终止条件： 当找到目标状态（正确排列）时，即 "12345678x"，输出当前步数；如果队列为空仍未找到目标状态，则输出 -1。

代码：

#include <iostream>
#include <unordered_map>
#include <queue>

using namespace std;

string str;
unordered_map<string, int>h;
queue<string>q;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int main() {
    for (int i = 0; i < 9; i ++ ) {
        char c;
        cin >> c;
        str += c;
    }
    h[str] = 0;
    q.push(str);
    while (!q.empty()) {
        string s = q.front();
        q.pop();

        int pos = s.find('x'), res = h[s];
        int a = pos / 3, b = pos % 3;
        if (s == "12345678x") {
            cout << res;
            return 0;
        }
        for (int i = 0; i < 4; i ++ ) {
            int ax = a + dx[i], by = b + dy[i];
            if (ax >= 0 && ax <= 2 && by >= 0 && by <= 2) {
                swap(s[pos], s[ax *3 + by]);
                if (h.find(s) == h.end()) {
                    h[s] = res + 1;
                    q.push(s);
                }
                swap(s[pos], s[ax *3 + by]);
            }
        }
    }
    cout << "-1";
}