【BFS最小步数】魔板题解

魔板题解

题目传送门

题目传送门

一、题目描述

Rubik先生发明了魔板的二维版本，这是一个有8个格子的板子，初始状态为：

1 2 3 4
8 7 6 5

我们可以用三种操作来改变魔板状态：

• A：交换上下两行
• B：将最右边一列插入到最左边
• C：魔板中央的4个数顺时针旋转

给定一个目标状态，要求找出从初始状态到目标状态的最短操作序列，如果有多个解，输出字典序最小的那个。

二、题目分析

这是一个典型的状态空间搜索问题，我们需要找到从初始状态到目标状态的最短路径。由于状态数量有限（8! = 40320种可能状态），可以使用广度优先搜索(BFS)来求解。

三、解题思路

1. 使用BFS从初始状态开始搜索
2. 对于每个状态，尝试三种操作生成新状态
3. 记录每个状态的来源和操作，以便最后回溯路径
4. 当找到目标状态时，根据记录的信息回溯操作序列
5. 由于BFS按层扩展，第一个找到的解就是最短的
6. 按照A、B、C的顺序尝试操作，保证字典序最小

四、算法讲解

广度优先搜索(BFS)

1. 算法原理：BFS是一种图搜索算法，它从起始节点开始，逐层向外扩展，直到找到目标节点。在状态空间搜索中，每个节点代表一个状态，边代表操作。
2. 使用场景：适用于寻找无权图中的最短路径问题，如本题中的最少操作次数。
3. 实现步骤：
   • 初始化队列，加入起始状态
   • 记录每个状态的访问情况和距离
   • 对于队列中的每个状态，尝试所有可能的操作
   • 将未访问过的新状态加入队列
   • 直到找到目标状态为止

结合例子

以样例输入2 6 8 4 5 7 3 1为例：

1. 初始状态：1 2 3 4 5 6 7 8
2. 通过BFS逐步扩展，最终找到目标状态
3. 回溯操作序列得到BCABCCB

五、代码实现

#include <bits/stdc++.h>
using namespace std;
string Start, End;
char g[2][4];
unordered_map<string, pair<char, string>> pre; // 记录前驱状态和操作
unordered_map<string, int> dist; // 记录距离// 将字符串表示的状态设置到二维数组中
void setString(string t)
{for (int i = 0; i < 4; i++)g[0][i] = t[i];for (int i = 7, j = 0; j < 4; i--, j++)g[1][j] = t[i];
}// 从二维数组获取字符串表示的状态
string getString()
{string res;for (int i = 0; i < 4; i++)res += g[0][i];for (int i = 3; i >= 0; i--)res += g[1][i];return res;
}// 操作A：交换上下两行
string move0(string t)
{setString(t);for (int i = 0; i < 4; i++)swap(g[0][i], g[1][i]);return getString();
}// 操作B：将最右边的一列插入到最左边
string move1(string t)
{setString(t);char v0 = g[0][3], v1 = g[1][3];for (int i = 3; i > 0; i--)g[0][i] = g[0][i - 1], g[1][i] = g[1][i - 1];g[0][0] = v0, g[1][0] = v1;return getString();
}// 操作C：魔板中央的4个数顺时针旋转
string move2(string t)
{setString(t);char v = g[0][1];g[0][1] = g[1][1];g[1][1] = g[1][2];g[1][2] = g[0][2];g[0][2] = v;return getString();
}// BFS搜索最短路径
int bfs(string Start, string end)
{if (Start == end)return 0;queue<string> q;q.push(Start);dist[Start] = 0;while (q.size()){auto t = q.front();q.pop();string m[3];m[0] = move0(t); // 尝试操作Am[1] = move1(t); // 尝试操作Bm[2] = move2(t); // 尝试操作Cfor (int i = 0; i < 3; i++)if (!dist.count(m[i])){dist[m[i]] = dist[t] + 1;pre[m[i]] = {'A' + i, t}; // 记录前驱和操作q.push(m[i]);if (m[i] == end)return dist[m[i]];}}return -1;
}void solve()
{for (int i = 0; i < 8; i++){int x;cin >> x;End += char(x + '0');}Start = "12345678"; // 初始状态int step = bfs(Start, End);cout << step << "\n";string res;while (End != Start){res += pre[End].first; // 获取操作End = pre[End].second; // 回溯到前驱状态}reverse(res.begin(), res.end()); // 反转得到正确顺序if (step > 0)cout << res << "\n";
}int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

六、重点细节

1. 状态表示：使用字符串表示魔板状态，前四个字符是第一行，后四个字符是第二行的逆序。
2. 操作实现：三种操作通过二维数组转换实现，注意操作C的旋转方向。
3. 字典序处理：按照A、B、C的顺序尝试操作，保证找到的第一个解就是字典序最小的。
4. 路径记录：使用pre哈希表记录每个状态的前驱和操作，便于回溯路径。
5. 边界处理：当初始状态就是目标状态时直接返回0。

七、复杂度分析

1. 时间复杂度：O(8!) = O(40320)，因为最多有8!种不同的状态。
2. 空间复杂度：O(8!)，需要存储所有可能状态的访问信息和前驱关系。

八、总结

本题通过BFS搜索状态空间，利用哈希表记录状态信息和路径，是一种典型的图搜索问题。关键在于：

1. 合理表示状态
2. 正确实现三种操作
3. 高效记录和回溯路径
4. 处理字典序要求

这种BFS方法适用于类似的"最少操作次数"问题，如八数码问题等。