。滑动拼图-php教程-PHP中文网

。滑动拼图

Mary-Kate Olsen

发布： 2024-12-02 07:39:10

原创

585 人浏览过

773。滑动拼图

难度：难

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

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

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

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

示例1：

. Sliding Puzzle

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

示例2：

. Sliding Puzzle

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

示例 3：

. Sliding Puzzle

输入： 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]都是唯一。

提示：

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

解决方案：

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

方法：

广度优先搜索（BFS）：
- BFS 在这里是理想的选择，因为我们正在寻找到达已解决状态的最短路径。
- 每个棋盘配置都可以被视为一个节点，节点之间的边代表有效的移动，其中 0 块与相邻块交换。
- BFS 将逐级探索棋盘配置，确保我们以最少的步数达到已解决的状态。
国家代表：
- 我们将把棋盘表示为字符串（以便于比较和存储）。
- 解决的状态是“123450”，因为它是棋盘 [[1,2,3],[4,5,0]] 的线性表示。
状态转换：
- 在每个状态中，如果 0 块位于棋盘的边界内，则它可以与其 4 个相邻块（上、下、左、右）之一交换。
跟踪访问过的州：
- 我们需要跟踪访问过的状态以避免循环和冗余计算。
检查已解决的状态：
- 如果在任何时候棋盘配置与已解决的状态匹配，我们都会返回到达该状态所需的移动次数。
处理不可能的情况：
- 如果 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。