グリッド内に少なくとも 1 つの有効なパスを作成するための最小コスト

1368年。グリッド内に少なくとも 1 つの有効なパスを作成するための最小コスト

難易度: 難しい

トピック: 配列、幅優先検索、グラフ、ヒープ (優先キュー)、行列、最短パス

m x n グリッドが与えられます。グリッドの各セルには、現在このセルにいる場合に訪問する必要がある次のセルを示す標識があります。 Grid[i][j] の符号は次のとおりです:

• 1 は、右のセルに移動することを意味します。 (つまり、grid[i][j] から Grid[i][j 1] に移動します)
• 2 は、左のセルに移動することを意味します。 (つまり、grid[i][j] から Grid[i][j - 1] に移動します)
• 3 は、下のセルに移動することを意味します。 (つまり、grid[i][j] から Grid[i 1][j] に移動します)
• 4 これは、上のセルに移動することを意味します。 (つまり、grid[i][j] から Grid[i - 1][j] に移動します)

グリッドのセル上には、グリッドの外側を指すいくつかの標識がある可能性があることに注意してください。

最初は左上のセル (0, 0) から開始します。グリッド内の有効なパスは、グリッド上の記号に従って、左上のセル (0, 0) から始まり右下のセル (m - 1, n - 1) で終わるパスです。有効なパスは最短である必要はありません。

コスト = 1 のセルの符号を変更できます。セルの符号は 1 回のみ変更できます。

グリッドに少なくとも 1 つの有効なパスを持たせるための最小コストを返します。

例 1:

• 入力: グリッド = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2] ]
• 出力: 3
• 説明: ポイント (0, 0) から開始します。 (3, 3) へのパスは次のとおりです。 (0, 0) --> (0, 1) --> (0, 2) --> (0, 3)
• コスト = 1 で矢印を下に変更します --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0)
• コスト = 1 で矢印を下に変更します --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3)
• コスト = 1 で矢印を下に変更します --> (3, 3) 合計コスト = 3.

例 2:

• 入力: グリッド = [[1,1,3],[3,2,2],[1,1,4]]
• 出力: 0
• 説明: (0, 0) から (2, 2) までのパスをたどることができます。

例 3:

• 入力: グリッド = [[1,2],[4,3]]
• 出力: 1

制約:

• m == グリッドの長さ
• n == グリッド[i].length
• 1
• 1

ヒント:

1. grid[i][j] が重み付きエッジを使用して 4 つの辺に隣接するセルすべてに接続されるグラフを構築します。重みは、記号が隣接するセルを指している場合は 0、それ以外の場合は 1 です。
2. 最初に重み = 0 のすべてのエッジを訪問して (0, 0) から BFS を実行します。答えは (m -1, n - 1) までの距離です。

解決策:

0-1 BFS アプローチを使用できます。このアイデアは、デキュー (両端キュー) を使用してグリッドを横断することです。方向を変更するコストによって、セルがデキューの前に追加されるか後ろに追加されるかが決まります。グリッドは、現在の方向が隣接するセルの動きと一致するかどうかに基づいて、各セルに重み付けされたエッジを持つグラフとして扱われます。

このソリューションを PHP で実装してみましょう: 1368。グリッド内に少なくとも 1 つの有効なパスを作成するための最小コスト

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

// Example Test Cases
$グリッド内に少なくとも 1 つの有効なパスを作成するための最小コスト = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]];
echo minCost($グリッド内に少なくとも 1 つの有効なパスを作成するための最小コスト) . "\n"; // Output: 3

$グリッド内に少なくとも 1 つの有効なパスを作成するための最小コスト = [[1,1,3],[3,2,2],[1,1,4]];
echo minCost($グリッド内に少なくとも 1 つの有効なパスを作成するための最小コスト) . "\n"; // Output: 0

$グリッド内に少なくとも 1 つの有効なパスを作成するための最小コスト = [[1,2],[4,3]];
echo minCost($グリッド内に少なくとも 1 つの有効なパスを作成するための最小コスト) . "\n"; // Output: 1
?>

説明：

1. 方向マッピング: 各方向 (1 は右、2 は左、3 は下、4 は上) は、移動デルタ [dx, dy] の配列にマッピングされます。

2. 0-1 BFS:

   • 両端キューは、コストの低いセルを優先するために使用されます。方向を変更する必要のないセルは前方に追加され (シフト解除)、変更が必要なセルは後方に追加されます (エンキュー)。
   • これにより、コストの昇順でセルが処理されることが保証されます。

3. 距離配列: 2D 配列 $dist は、各セルに到達するための最小コストを追跡します。開始セル (0, 0) を除くすべてのセルに対して PHP_INT_MAX で初期化されます。

4. エッジの重み:

   • 現在のセルの符号が意図した方向と一致する場合、コストは変わりません。
   • それ以外の場合、方向を変更するとコスト 1 が発生します。

5. 終了: すべてのセルが処理されるとループは終了します。結果は $dist[$m - 1][$n - 1] の値で、右下隅に到達するまでの最小コストを表します。

複雑：

• 時間計算量: O(m × n)、各セルは 1 回処理されるため。
• 空間複雑度: O(m × n)、距離配列と両端キューの場合。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

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

• LinkedIn
• GitHub

以上がグリッド内に少なくとも 1 つの有効なパスを作成するための最小コストの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。