。スライディングパズル

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

難易度: 難しい

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

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

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

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

例 1:

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

例 2:

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

例 3:

• 入力: ボード = [[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]は一意です。

ヒント:

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

解決策:

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

アプローチ：

1. 幅優先検索 (BFS):

   • 解決された状態への最短パスを探しているため、ここでは BFS が理想的です。
   • 各ボード構成はノードと見なすことができ、ノード間のエッジは、0 タイルが隣接するタイルと交換される有効な手を表します。
   • BFS はボード構成をレベルごとに調査し、最小限の移動数で解決済み状態に到達できるようにします。

2. 州の代表:

   • ボードを文字列として表します (比較と保存を容易にするため)。
   • ボード [[1,2,3],[4,5,0]] の線形表現であるため、解決された状態は「123450」になります。

3. 状態遷移:

   • 各状態から、ボードの境界内にある場合、0 タイルはその 4 つの隣接タイル (上、下、左、右) の 1 つと交換できます。

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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。スライディングパズルの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。