。スライディングパズル-PHPチュートリアル-php.cn

。スライディングパズル

Mary-Kate Olsen

リリース： 2024-12-02 07:39:10

オリジナル

594 人が閲覧しました

773。スライディングパズル

難易度: 難しい

トピック: 配列、幅優先検索、行列

2 x 3 ボードには、1 から 5 までのラベルが付けられた 5 つのタイルと、0 で表される空の正方形があります。移動は、0 と 4 方向に隣接する数字を選択し、それを交換することで構成されます。 .

ボードの状態は、ボードが [[1,2,3],[4,5,0]] である場合にのみ解決されます。

パズルボードのボードが与えられた場合、ボードの状態を解決するために必要な最小の移動数を返します。ボードの状態を解決できない場合は、-1 を返します。

例 1:

. Sliding Puzzle

入力: ボード = [[1,2,3],[4,0,5]]
出力: 1
説明: 0 と 5 を 1 回の動作で交換します。

例 2:

. Sliding Puzzle

入力: ボード = [[1,2,3],[5,4,0]]
出力: -1
説明: 何回動かしてもボードは解決されません。

例 3:

. Sliding Puzzle

入力: ボード = [[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
board[i].length == 3
0
各値board[i][j]は一意です。

ヒント:

幅優先検索を実行します。2 つのパズルボードを 1 回の移動で相互に変換できる場合、ノードはパズルボード、エッジはエッジとなります。

解決策:

幅優先検索 (BFS) アルゴリズムを適用できます。このアイデアは、与えられた初期状態から開始して、解決された状態に到達するまで、一度に 1 つずつ移動しながら、ボードのすべての可能な構成を探索することです。

アプローチ：

幅優先検索 (BFS):
- 解決された状態への最短パスを探しているため、ここでは BFS が理想的です。
- 各ボード構成はノードと見なすことができ、ノード間のエッジは、0 タイルが隣接するタイルと交換される有効な手を表します。
- BFS はボード構成をレベルごとに調査し、最小限の移動数で解決済み状態に到達できるようにします。
州の代表:
- ボードを文字列として表します (比較と保存を容易にするため)。
- ボード [[1,2,3],[4,5,0]] の線形表現であるため、解決された状態は「123450」になります。
状態遷移:
- 各状態から、ボードの境界内にある場合、0 タイルはその 4 つの隣接タイル (上、下、左、右) の 1 つと交換できます。
訪問国の追跡:
- サイクルや冗長な計算を避けるために、訪問した州を追跡する必要があります。
解決状態の確認:
- いずれかの時点でボードの構成が解決された状態と一致する場合、そこに到達するまでにかかった手の数を返します。
不可能なケースの処理:
- 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 を返します。