P1379 八数码难题

题目描述

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

283104765

输出 #1

说明/提示

样例解释

图中展示了样例当中从初始状态到目标状态的一种方案，共需要 \(4\) 步。

并且可以证明，不存在更优的策略。

Tip

b站讲解

📌 题目分析

给定数据： * 一个 \(3 \times 3\) 的棋盘，包含 \(1 \sim 8\) 的数字和空格 0。 * 每次可以将 0 与其上下左右的数字交换。 * 目标状态固定为：123804765。

👉 本质： 求全排列状态空间中的单源最短路径。

👉 类型： 广度优先搜索 (BFS) + 哈希去重 (Hash Map) / A* 搜索。

🧠 解题思路

1️⃣ 为什么求“最少步骤”首选 BFS？

我们在之前的网格地图题中强调过，求无权图的最少步数/最短路径，BFS 是唯一的正解。这道题的特别之处在于，它的“图”不是一张普通的二维网格，而是一张状态转移图。每一个完整的 \(3 \times 3\) 棋盘布局，就是图上的一个“节点”；把 0 往旁边移动一步产生的新布局，就是相邻的“节点”。从初始布局扩散到目标布局，最先到达的波纹必定经历最少的移动次数。

2️⃣ 状态的极简表示（降维打击）

如果在队列中存一个 \(3 \times 3\) 的二维数组，不仅占用空间极大，而且很难判重（判断这个状态之前有没有搜过）。 神仙操作：字符串降维。 将 \(3 \times 3\) 的数字直接拼接成一个长度为 9 的字符串（例如 "283104765"）。利用 C++ 的 std::unordered_map<string, int> dist，我们就可以完美地建立起：“棋盘布局状态” \(\to\) “到达该状态的最少步数” 的映射关系。

3️⃣ 一维与二维坐标的无缝转换

字符串是一维的，但 0 的移动是二维的（上下左右）。假设 0 在字符串中的下标为 idx（范围 \(0 \sim 8\)），它在 \(3 \times 3\) 网格中的二维坐标 (x, y) 可以通过数学公式直接得出： * x = idx / 3 （行号，除以列数） * y = idx % 3 （列号，对列数取余）

移动后的新坐标 (nx, ny)，再转回一维下标： * new_idx = nx * 3 + ny 然后直接在字符串上调用 swap(s[idx], s[new_idx]) 即可产生新状态！

💻 C++代码

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

using namespace std;

// 方向数组：上下左右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int main() {
    // 提升 I/O 速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string start;
    cin >> start;

    string target = "123804765";

    // 终点和起点相同，直接 0 步
    if (start == target) {
        cout << 0 << "\n";
        return 0;
    }

    // BFS 核心数据结构
    queue<string> q;
    unordered_map<string, int> dist; // 记录状态以及到达该状态的最少步数

    // 初始化
    q.push(start);
    dist[start] = 0;

    while (!q.empty()) {
        string curr = q.front();
        q.pop();

        int step = dist[curr];

        // 如果到达目标状态，立刻输出并结束程序
        if (curr == target) {
            cout << step << "\n";
            return 0;
        }

        // 1. 找到 '0' 在一维字符串中的位置
        int idx = curr.find('0');

        // 2. 将一维下标转换为 3x3 的二维坐标
        int x = idx / 3;
        int y = idx % 3;

        // 3. 尝试向上下左右四个方向移动 '0'
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 检查边界
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                // 将二维坐标转回一维下标
                int new_idx = nx * 3 + ny;

                // 产生新的状态字符串
                string next_state = curr;
                swap(next_state[idx], next_state[new_idx]);

                // 如果这个新状态之前没有走到过 (未在 map 中出现)
                if (!dist.count(next_state)) {
                    dist[next_state] = step + 1; // 步数 +1
                    q.push(next_state);
                }
            }
        }
    }

    return 0;
}

⚠️ 易错点

错用 map 而非 unordered_map： C++ 的 std::map 底层是红黑树，每次插入/查询字符串的时间复杂度是 \(O(\text{len} \times \log N)\)；而 std::unordered_map 底层是哈希表，平均时间复杂度是 \(O(\text{len})\)。八数码状态空间达到 \(36\) 万，使用 unordered_map 会显著提升运行速度。
每次循环修改了当前字符串： 在进行上下左右 4 次试探时，每次都必须用一个临时字符串 string next_state = curr; 来接管，否则你在向左换完 0 之后直接向右换，棋盘就乱套了。
未做起始状态特判： 虽然很少见，但如果出题人给的输入数据直接就是 123804765，如果不加特判，可能会导致不必要的队列开销。

🚀 一句话总结

将棋盘降维成 9 位字符串，利用队列层层扩展状态转移图，借助哈希表去重并记录步数，搜到目标即是最短路径。

🔥 补充：硬核知识点

如果将这道题扩展到 15 数码难题 (\(4 \times 4\)) 甚至更大，状态数会从 \(9! = 362,880\) 暴增到 \(16! \approx 2 \times 10^{13}\)，普通 BFS 必将爆内存 + TLE。此时我们需要更高阶的算法武器：

1. 双向 BFS (Bidirectional BFS) 由于起点和终点状态都是明确已知的，我们可以同时从起点（正向）和终点（反向）开始往中间搜。 * 单向 BFS 的搜索树是一个庞大的倒三角。 * 双向 BFS 的搜索树是两个小倒三角，当它们在中间某一状态相遇时（即某个 string 同时出现在正向和反向的 map 中），把两边的步数相加就是答案。这可以把指数级的底数开根号，速度提升成百上千倍。

2. A* 启发式搜索与曼哈顿距离 这题是 A 算法的完美练习场。我们可以设计估价函数 \(h(state)\) 为：当前棋盘上所有非 0 数字，距离它们最终目标位置的“曼哈顿距离”之和*。曼哈顿距离越小，说明这个盘面“看起来”越接近终点。用优先队列每次挑选 \(g(x) + h(x)\) 最小的状态进行扩展，能极大缩减无效搜索的分支。

3. 八数码的有解性判定（逆序对的奇偶性） 这是一个纯数学结论：把棋盘上的数字（忽略 0）从左到右、从上到下排成一列。每次合法的左右交换不改变逆序对总数的奇偶性，上下交换在 \(3 \times 3\) 棋盘中相当于跨越 2 个数字，同样不改变逆序对的奇偶性。因此，任意一个布局的逆序对奇偶性是永远固定的！如果不通过搜索，只需对比初始状态和目标状态的逆序对奇偶性是否一致，就能在 \(O(N \log N)\) 瞬间判定这道题到底有没有解！