DEV Community
·
773. 滑动拼图
💡
原文英文，约800词，阅读约需3分钟。
📝
内容提要
在一个2x3的滑动拼图中，有5个数字和一个空格。目标是通过交换空格与相邻数字，达到状态[[1,2,3],[4,5,0]]。使用广度优先搜索（BFS）算法探索所有可能的配置，返回最少移动次数，若无法解决则返回-1。
🎯
关键要点
- 在一个2x3的滑动拼图中，有5个数字和一个空格，目标是达到状态[[1,2,3],[4,5,0]]。
- 通过交换空格与相邻数字，返回最少移动次数，若无法解决则返回-1。
- 使用广度优先搜索（BFS）算法探索所有可能的配置。
- 每个拼图配置可以视为一个节点，节点之间的边表示有效的移动。
- BFS逐层探索拼图配置，确保以最少的移动次数达到解决状态。
- 将拼图状态表示为字符串，以便于比较和存储。
- 0块可以与其四个邻居交换，前提是它在拼图的边界内。
- 需要跟踪已访问的状态，以避免循环和冗余计算。
- 如果找到解决状态，返回所需的移动次数；否则返回-1。
- 时间复杂度为O(N)，空间复杂度也为O(N)，N为唯一拼图状态的数量。
➡️
