八数码问题

04 Sep 2024 in Algorithm Pageviews

bfs

在一个3 x 3 的网格中，1 ~ 8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3 x 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 x 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

代码实现如下:

#include <bits/stdc++.h>

using namespace std;

int bfs(const string &start)
{
    string end = "12345678x";
    unordered_map<string, int> dis;
    dis[start] = 0;
    queue<string> que;
    que.push(start);
    vector<int> dir{-1, 0, 1, 0, -1};

    while (!que.empty()) {
        auto f = que.front();
        que.pop();
        int d = dis[f];
        if (f == end) {
            return d;
        }

        int k = f.find('x');
        int x = k / 3;
        int y = k % 3;
        for (int i = 0; i < 4; i++) {
            int x_ = x + dir[i];
            int y_ = y + dir[i + 1];
            if (x_ < 0 || x_ >= 3 || y_ < 0 || y_ >= 3) {
                continue;
            }

            swap(f[k], f[x_ * 3 + y_]);
            if (dis.count(f) == 0) {
                dis[f] = d + 1;
                que.push(f);
            }
            swap(f[k], f[x_ * 3 + y_]);
        }
    }
    return -1;
}

int main()
{
    string state;
    for (int i = 0; i < 9; i++) {
        char c;
        cin >> c;
        state += c;
    }
    cout << bfs(state) << endl;
    return 0;
}