ACWing 179 八数码题解

2025 年 02 月 26 日

29 次浏览

2453字数

# 题目描述

在 $3\times 3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 $0$ 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 $123804765$），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

# 输入格式

输入初始状态，一行九个数字，空格用 $0$ 表示。

# 输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

# 解题思路

本题考虑使用 **A***算法减少搜索到的状态的数量

## A*算法

### 使用条件

- 从起点$x$到终点$y$存在解
- 设从起点$x$出发搜索到点$u$, 设点$u$到终点$y$的真实距离为$g(u)$, 估计距离为$f(u)$, 则应该有$f(u) \leq g(u)$

### 算法流程

- 使用小根堆存储遍历过程中的顶点
- 记录每个顶点的离起点的距离`dist`
- 当堆不为空时：
  - 弹出堆顶
  - 如果堆顶元素为目标元素， 跳出循环
  - 遍历其可以到达的元素，如果可以到达的元素没被遍历过或者虽然遍历过，但记录的距离dist大于本次遍历的距离， 则更新距离并入队

### 算法特点

- 只可以保证目标元素的最小距离， 经过的元素无法保证最小距离
- 出队的时候才可以得到最小距离

# AC代码

```cpp
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <unordered_map>
#include <algorithm>
#define endl '\n'
using namespace std;
typedef pair<int, string> PIS;
const int N = 2e5 + 10;

string input, ans = "12345678x";
priority_queue<PIS, vector<PIS>, greater<PIS>> heap;
unordered_map<string, int> dist;
unordered_map<string, pair<string, char>> pre;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
char op[] = "urdl";

int f(string state)
{
    int cnt = 0;
    for(int i = 0; i < 9; i ++)
    {
        if(state[i] != 'x')
        {
            int t = state[i] - '1';
            cnt += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }
    }
    return cnt;
}

string bfs()
{
    heap.push({f(input), input});
    dist[input] = 0;
    pre[input] = {"no", 'E'};

while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

string state = t.second;
        int d = dist[state];

if(state == ans) break;

int x, y;
        for(int i = 0; i < 9; i ++)
        {
            if(state[i] == 'x')
            {
                x = i / 3;
                y = i % 3;
                break;
            }
        }

for(int i = 0; i < 4; i ++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
            string nstate = state;
            swap(nstate[x * 3 + y], nstate[nx * 3 + ny]);
            if(dist.count(nstate) && dist[nstate] <= d + 1) continue;
            dist[nstate] = d + 1;
            pre[nstate] = {state, op[i]};
            heap.push({dist[nstate] + f(nstate), nstate});
        }

}

string res;
    while(pre[ans].second != 'E')
    {
        res += pre[ans].second;
        ans = pre[ans].first;
    }
    reverse(res.begin(), res.end());
    return res;

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
    char c;
    for(int i = 1; i <= 9; i ++)
    {
        cin >> c;
        input += c;
    }

int cnt = 0;
    for(int i = 0; i < 9; i ++)
    {
        if(input[i] == 'x') continue;
        for(int j = i + 1; j < 9; j ++)
        {
            if(input[j] == 'x') continue;
            if(input[i] > input[j]) cnt ++;
        }
    }

if(cnt % 2) cout << "unsolvable" << endl;
    else cout << bfs() << endl;

return 0;
}
```

最后修改：2025 年 02 月 26 日