Luobuyu's Blog

0%

179.八数码

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 2.2k 阅读时长 ≈ 2 分钟
使用A星进行搜索，比较简单，注意可行性判断

179. 八数码

题目描述：

在 $ 3 \times 3 $ 的棋盘上，摆有八个棋子，每个棋子上标有 $ 1 $ 至 $ 8 $ 的某一数字。棋盘中留有一个空格，空格用 X 来表示。空格周围的棋子可以移到空格中，这样原来的位置就会变成空格。给出一种初始布局和目标布局（为了使题目简单，设目标状态如下），找到一种从初始布局到目标布局最少步骤的移动方法。

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

数据范围：

题解：

可以使用双向 bfs ，也可以直接使用 A* ，使用 A* 的话，估价函数中， h(x) 设为从当前状态到目标状态的曼哈顿距离，g(x) 为起点到当前状态的真实距离，f(x) = g(x) + h(x) ，根据 f(x) 的值，小根堆排序。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
string e = "12345678x";
string s;
char op[] = "urdl";
unordered_map<string, int> g;
unordered_map<string, pair<string, char>> pre;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int getDis(int x, int t)
{
    return abs(x / 3 - t / 3) + abs(x % 3 - t % 3);
}

// 求曼哈顿距离
int getH(string s)
{
    int ret = 0;
    for (int i = 0; i < 9; i++)
    {
        if (s[i] != 'x')
        {
            // 注意 0-8
            ret += getDis(s[i] - '1', i);
        }
    }
    return ret;
}
// 放 fx
// 同时需要记录实际距离，每次计算估计距离
void bfs()
{
    priority_queue<pair<int, string>> q;
    q.push({-getH(s), s});
    g[s] = 0;
    while (q.size())
    {
        auto out = q.top();
        q.pop();
        string u = out.second;
        if (u == e)
            break;
        int gu = g[u];
        int index = u.find('x');
        int x = index / 3, y = index % 3;
        string tmp = u;
        for (int i = 0; i < 4; i++)
        {
            int newx = x + dx[i], newy = y + dy[i];
            if (newx < 0 || newx >= 3 || newy < 0 || newy >= 3)
                continue;
            swap(u[newx * 3 + newy], u[index]);
            if (!g.count(u) || g[u] > g[tmp] + 1)
            {
                g[u] = g[tmp] + 1;
                q.push({-g[u] - getH(u), u});
                pre[u] = {tmp, op[i]};
            }
            swap(u[newx * 3 + newy], u[index]);
        }
    }
}

int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    string tmps;
    char ch;
    for (int i = 1; i <= 9; i++)
    {
        cin >> ch;
        s += ch;
        if (ch != 'x')
        {
            tmps += ch;
        }
    }
    int cnt = 0;
    for (int i = 0; i < 8; i++)
    {
        for (int j = i + 1; j < 8; j++)
        {
            if (tmps[i] > tmps[j])
                cnt++;
        }
    }
    if (cnt & 1)
    {
        puts("unsolvable");
    }
    else
    {
        bfs();
        string ans;
        while (e != s)
        {
            ans += pre[e].second;
            e = pre[e].first;
        }
        reverse(ans.begin(), ans.end());
        cout << ans << endl;
    }
    return 0;
}