🪴 Edwin Aze's Blog

最近文章

最近笔记

八数码

6分钟阅读

179. 八数码 - AcWing题库

在一个  的网格中， 这  个数字和一个 X 恰好不重不漏地分布在这  的网格中。

例如：

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

把 X 与上下左右方向数字交换的行动记录为 u、d、l、r。

现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

输入格式

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

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

1 2 3 
x 4 6 
7 5 8

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

输出格式

输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。

如果答案不唯一，输出任意一种合法方案即可。

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

输入样例：

2  3  4  1  5  x  7  6  8

输出样例

ullddrurdllurdruldr

思路

用一个字符串表示八数码当前状态, 每次扩展当前状态时, 先遍历一遍找到当前x所在位置, 然后再进行上下走右交换, 得出的新串判断是否为之前枚举过的, 若不是则加入队列继续扩展, 直到目标状态出队。

相比于普通BFS, 这里还可以使用 A-star 算法。 将队列更改为小根堆, 每个状态的权值为当前走过的步数+未来要走的预期步数。每次扩展时用堆顶元素更新能走到的所有状态, 类似于dijkstra, 如果没走过或者走过去更优的话就更新。

预期函数则通过计算各位置的曼哈顿距离。

输出方案的话就直接用prev记录上一步更新的方向即可。

无解判断的话有些麻烦, 想不出来的话就直接time.h判断是否超过0.9s即可。

if((double)(clock() - st)/CLOCKS_PER_SEC > 0.9) return "-1";

正确推理的话, 因为每次移动只能改变两个逆序对, 不存在改变一个逆序对的情况, 故可以通过计算所有逆序对的和, 若为偶数则有解, 奇数则无解。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <unordered_map>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, string> PIS;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
 
int f(string state)
{
    // 12345678
    int res = 0;
    for (int i = 0; i < state.size(); i++)
    {
        if (state[i] != 'x')
        {
            int t = state[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }
    }
    return res;
}
 
string bfs(string start)
{
    string end = "12345678x";
    char op[] = "udlr";
    unordered_map<string, int> dist;
    unordered_map<string, PIS> prev;
    priority_queue<PIS, vector<PIS>, greater<PIS>> heap;
 
    heap.push({0 + f(start), start});
    dist[start] = 0;
    while (!heap.empty())
    {
        auto t = heap.top();
        heap.pop();
 
        string state = t.y;
        if (state == end)
            break;
        int x, y;
        for (int i = 0; i < state.size(); i++)
        {
            if (state[i] == 'x')
            {
                x = i / 3, y = i % 3;
                break;
            }
        }
        string source = state;
        for (int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a > 2 || b < 0 || b > 2)
                continue;
            state = source;
            swap(state[a * 3 + b], state[x * 3 + y]);
            if (dist.count(state) == 0 || dist[state] > dist[source] + 1)
            {
                dist[state] = dist[source] + 1;
                prev[state] = {i, source};
                heap.push({f(state) + dist[state], state});
            }
        }
    }
 
    string res;
    while (end != start)
    {
        res += op[prev[end].x];
        end = prev[end].y;
    }
    reverse(res.begin(), res.end());
    return res;
}
 
int main()
{
    string start, stp;
    char c;
    while (cin >> c)
    {
        start += c;
        if (c != 'x')
            stp += c;
    }
    int cnt = 0;
    for (int i = 0; i < 8; i++)
        for (int j = i; j < 8; j++)
            if (stp[i] > stp[j])
                cnt++;
    if (cnt & 1)
        cout << "unsolvable\n";
    else
        cout << bfs(start) << endl;
 
    return 0;
}

反向链接