。滑动拼图

773。滑动拼图

难度：难

主题：数组、广度优先搜索、矩阵

在 2 x 3 的棋盘上，有五个从 1 到 5 标记的图块，以及一个用 0 表示的空方块。 移动 包括选择 0 和 4 个方向相邻的数字并交换它.

当且仅当棋盘为 [[1,2,3],[4,5,0]] 时，棋盘的状态才得以解决。

给定拼图板，返回解决该板的状态所需的最少移动次数。如果棋盘状态无法求解，则返回-1。

示例1：

• 输入： board = [[1,2,3],[4,0,5]]
• 输出： 1
• 说明：一步交换 0 和 5。

示例2：

• 输入： board = [[1,2,3],[5,4,0]]
• 输出： -1
• 说明：无论移动多少步都无法解决棋盘问题。

示例 3：

• 输入： board = [[4,1,2],[5,0,3]]
• 输出： 5
• 说明： 5 是解决棋盘问题的最小步数。
  • 示例路径：
  • 第 0 步后：[[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]]

约束：

• board.length == 2
• 板[i].length == 3
• 0
• 每个值板[i][j]都是唯一。

提示：

1. 执行广度优先搜索，其中节点是拼图板，边缘是如果两个拼图板可以通过一次移动相互转换。

解决方案：

我们可以应用广度优先搜索（BFS）算法。这个想法是从给定的初始状态开始探索棋盘的所有可能配置，一次一步，直到达到已解决的状态。

方法：

1. 广度优先搜索（BFS）：

   • BFS 在这里是理想的选择，因为我们正在寻找到达已解决状态的最短路径。
   • 每个棋盘配置都可以被视为一个节点，节点之间的边代表有效的移动，其中 0 块与相邻块交换。
   • BFS 将逐级探索棋盘配置，确保我们以最少的步数达到已解决的状态。

2. 国家代表：

   • 我们将把棋盘表示为字符串（以便于比较和存储）。
   • 解决的状态是“123450”，因为它是棋盘 [[1,2,3],[4,5,0]] 的线性表示。

3. 状态转换：

   • 在每个状态中，如果 0 块位于棋盘的边界内，则它可以与其 4 个相邻块（上、下、左、右）之一交换。

4. 跟踪访问过的州：

   • 我们需要跟踪访问过的状态以避免循环和冗余计算。

5. 检查已解决的状态：

   • 如果在任何时候棋盘配置与已解决的状态匹配，我们都会返回到达该状态所需的移动次数。

6. 处理不可能的情况：

   • 如果 BFS 完成并且我们没有找到已解决的状态，则意味着不可能解决该难题，我们返回 -1。

让我们用 PHP 实现这个解决方案：773。滑动拼图

<?php
/**
 * @param Integer[][] $board
 * @return Integer
 */
function slidingPuzzle($board) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$board1 = [[1, 2, 3], [4, 0, 5]];
echo slidingPuzzle($board1);  // Output: 1

$board2 = [[1, 2, 3], [5, 4, 0]];
echo slidingPuzzle($board2);  // Output: -1

$board3 = [[4, 1, 2], [5, 0, 3]];
echo slidingPuzzle($board3);  // Output: 5
?>

解释：

• 初始设置：我们首先将 2D 板转换为 1D 字符串，以便于操作。
• BFS 执行： 我们将棋盘的初始状态和移动计数（从 0 开始）一起放入队列。在每次 BFS 迭代中，我们探索可能的移动（基于 0 块的位置），将 0 与相邻块交换，并将新状态放入队列。
• 访问过的状态：我们使用字典来跟踪访问过的棋盘状态，以避免重新访问和循环回相同的状态。
• 边缘验证：我们检查任何移动是否保留在 2x3 网格的边界内，特别是确保没有非法移动环绕网格（例如在左边缘向左移动或在右边缘向右移动）。
• 返回结果：如果我们达到目标状态，我们将返回移动次数。如果 BFS 完成但我们没有达到目标，我们返回 -1。

时间复杂度：

• BFS 复杂度： BFS 的时间复杂度为 O(N)，其中 N 是唯一棋盘状态的数量。对于这个谜题，最多有 6 个！ (720) 可能的配置。

空间复杂度：

• 由于队列和访问状态所需的存储空间复杂度也是 O(N)。

考虑到限制，该解决方案应该足够高效。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是。滑动拼图的详细内容。更多信息请关注PHP中文网其他相关文章！