【C/C++】滑动谜题（leetcode T773）

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.

最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

重点通过测试用例来理解题目：

示例 1：

输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5 ，1 步完成

示例 2:

输入：board = [[1,2,3],[5,4,0]]
输出：-1
解释：没有办法完成谜板

示例 3:

输入：board = [[4,1,2],[5,0,3]]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]

题目详解：

class Solution {
private:// 定义每个位置与可以交换的相邻位置vector<vector<int>> neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};// neighbors[x] 表示数字 x 所在位置与它可以交换的位置
public:int slidingPuzzle(vector<vector<int>>& board) {// 枚举状态，通过一次交换操作得到的状态auto get = [&](string& status) -> vector<string> {vector<string> ret;int x = status.find('0');  // 找到空缺的位置（数字 0）for (int y : neighbors[x]) {  // 遍历可以与 0 交换的位置swap(status[x], status[y]);  // 交换位置ret.push_back(status);  // 记录交换后的状态swap(status[x], status[y]);  // 再交换回来，保持原样}return ret;};// 将二维板转换为字符串形式，方便进行状态比较和转移string initial;for (int i = 0; i < 2; i++) {for (int j = 0; j < 3; j++) {initial += char(board[i][j] + '0');  // 将数字转为字符}}// 如果初始状态已经是目标状态 "123450"，返回 0 步if (initial == "123450") {return 0;}// 使用 BFS 队列进行状态的广度优先搜索，保存当前状态和步数queue<pair<string, int>> q;q.emplace(initial, 0);// 哈希集合记录已经访问过的状态，避免重复搜索unordered_set<string> seen = {initial};// BFS 主循环while (!q.empty()) {auto [status, step] = q.front();q.pop();// 获取当前状态的所有可能后继状态for (auto&& next_status : get(status)) {if (!seen.count(next_status)) {  // 如果该状态没有被访问过if (next_status == "123450") {  // 找到目标状态return step + 1;}// 将新状态加入队列，步数 + 1q.emplace(next_status, step + 1);seen.insert(move(next_status));  // 将新状态标记为已访问}}}// 如果所有状态都搜索完毕还没有找到目标状态，返回 -1return -1;}
};

语法补充：

1.结构化绑定

（Structured Binding）它用于从 pair（或 tuple）等类型中直接解包多个值。这个语法是在 C++17 引入的。 

auto [status, step] = q.front();

相当于，可以简化代码：

pair<string, int> p = q.front();  // 取出队首元素
string status = p.first;  // 获取状态
int step = p.second;  // 获取步数

2.辅助函数：Lambda函数

具体可看文章：【C++基础】Lambda 函数 基础知识讲解学习及难点解析-CSDN博客

思路分析：

1. 题目分析： 这个问题是一个经典的 状态转移问题，可以通过 广度优先搜索 (BFS) 来解决。我们需要在一个 2x3 的谜板中，进行数字的交换，使得最终的状态变成 [[1,2,3],[4,5,0]]。目标是找到解锁该谜板所需的最小步数。如果无法解锁，则返回 -1。

2. 基本思路：

   • 状态表示：使用一个字符串来表示谜板的状态，方便进行状态之间的转移。例如，初始状态 board = [[1,2,3],[4,5,0]] 可以表示为字符串 "123450"。

   • 广度优先搜索：从初始状态出发，逐步扩展每一步的状态，直到找到目标状态 "123450"，同时记录每个状态的步数。通过队列来保存待探索的状态，每次从队列中取出当前状态，生成所有可能的后继状态，并将未访问过的状态加入队列。

   • 状态转移：从当前状态出发，找到空白 0 所在的位置，然后交换 0 与它的相邻位置上的数字。每一次交换得到一个新的状态。

   • 优化：使用哈希集合 seen 来记录已经访问过的状态，避免重复计算。

3. 具体步骤：

   • 将二维谜板 board 转换为一个字符串 initial，方便后续的状态比较和操作。

   • 如果初始状态已经是目标状态 "123450"，则返回 0，因为不需要任何操作。

   • 使用 BFS 从初始状态开始进行广度优先搜索，队列中存储当前状态及步数。

   • 对于每个状态，生成所有可能的后继状态，如果后继状态是目标状态，则返回当前步数 + 1。

   • 如果所有状态都搜索完毕而没有找到目标状态，则返回 -1。

4. 时间和空间复杂度：

   • 时间复杂度：每个状态的转移涉及到常数个操作，因此时间复杂度主要由状态数量决定。状态空间大小为 6!（即 720），因此时间复杂度为 O(720)，即在最大状态数下，BFS 的复杂度是 O(N)，其中 N 是状态的个数。

   • 空间复杂度：BFS 使用队列和哈希集合来存储状态，空间复杂度也是 O(N)，即 O(720)。