グリッド内のセルを訪問するための最小時間

2577。グリッド内のセルにアクセスするための最小時間

難易度: 難しい

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

非負の整数で構成される m x n 行列グリッドが与えられます。ここで、grid[row][col] はセル (行、これは、セル (行、列) にアクセスした時間がそれ以降である場合にのみ、セル (行、列) にアクセスできることを意味します。グリッド[行][列]. あなたは 0

番目

秒目に行列の 左上 セルに立っており、4 番目の^いずれか の隣接するセルに移動する必要があります。方向: 上、下、左、右。各動作には 1 秒かかります。 行列の右下のセルにアクセスするために必要な

最小

時間を返します。右下のセルにアクセスできない場合は、-1 を返します。

例 1:

入力:
• グリッド = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
出力:
• 7
説明:
• 選択できるパスの 1 つは次のとおりです。 t = 0 では、セル (0,0) にいます。
  • t = 1 で、セル (0,1) に移動します。 Grid[0][1] であるため、それは可能です。
  • t = 2 で、セル (1,1) に移動します。 Grid[1][1] であるため、それは可能です。
  • t = 3 で、セル (1,2) に移動します。 Grid[1][2] であるため、それは可能です。
  • t = 4 で、セル (1,1) に移動します。 Grid[1][1] であるため、それは可能です。
  • t = 5 で、セル (1,2) に移動します。 Grid[1][2] であるため、それは可能です。
  • t = 6 で、セル (1,3) に移動します。 Grid[1][3] であるため、それは可能です。
  • t = 7 で、セル (2,3) に移動します。 Grid[2][3] であるため、それは可能です。
  • 最終時間は 7 です。これは可能な最小時間であることがわかります。

例 2:

入力:
• グリッド = [[0,2,4],[3,2,1],[1,0,4]]
出力:
• -1
説明:
• 左上から右下のセルへのパスがありません。

制約:

m == グリッドの長さ

• n == グリッド[i].length
• 2
• 4 sup>5
• 0 sup>5
• グリッド[0][0] == 0

ヒント:

1. グラフ上の最短経路を見つけることができるアルゴリズムを使用してみてください。
2. 他のセルのロックを解除するために行列の 2 つのセル間を行ったり来たりする必要がある場合を考えてみましょう。

解決策:

優先キューを使用して、ダイクストラのアルゴリズムの修正バージョンを適用できます。この問題は基本的に、左上のセルから右下のセルに移動するのに必要な最短時間を見つけることを求めます。各移動にはグリッド内の値に基づく時間制約があります。

アプローチ：

1. グラフ表現: グリッド内の各セルをノードとして扱います。エッジは、移動できる隣接するセル (上下左右) です。

2. 優先キュー (最小ヒープ): 優先キューを使用して、常に最小限の時間でセルを探索します。これにより、セルに到達できる最も早い時間から順にセルが処理されるようになります。

3. 修正 BFS: 各セルについて、隣接するセルに移動できるかどうかを確認し、それらのセルにアクセスできる時間を更新します。セルが現在よりも遅い時間にアクセスされた場合、新しい時間でセルをキューに追加し直します。

4. Early Exit: 右下のセルに到達したら、時間を戻すことができます。キューに到達せずにキューを使い果たした場合は、-1 を返します。

このソリューションを PHP で実装してみましょう: 2577。グリッド内のセルにアクセスするための最小時間

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

// Example 1
$grid1 = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid1) . PHP_EOL; // Output: 7

// Example 2
$grid2 = [
    [0, 2, 4],
    [3, 2, 1],
    [1, 0, 4]
];
echo minimumTime($grid2) . PHP_EOL; // Output: -1
?>

説明：

1. 優先キュー:
   
   SplPriorityQueue は、最小時間のセルが最初に処理されるようにするために使用されます。 PHP の SplPriorityQueue はデフォルトで最大ヒープであるため、優先度は -time として保存されます。

2. トラバーサル:
   
   アルゴリズムは、左上のセル (0, 0) から開始して、各セルにアクセスできる最も早い時間を考慮して、到達可能なすべてのセルを処理します (max(0, Grid[newRow][newCol] - (time 1)))。

3. 訪問したセル:
   
   訪問された配列は、冗長な計算や無限ループを避けるために、すでに処理されたセルを追跡します。

4. 境界と有効性チェック:
   
   このアルゴリズムにより、グリッドの境界内に留まり、有効な近傍のみが処理されるようになります。

5. 時間計算:
   
   各移動には 1 秒かかり、セルが待機する必要がある場合 (つまり、grid[newRow][newCol] > time 1)、アルゴリズムは必要な時間まで待機します。

6. エッジケース:
   
   キューが使い果たされ、右下のセルに到達しない場合、関数は -1 を返します。

---

複雑さの分析

1. 時間計算量:

   • 各セルは最大 1 回優先キューに追加されます: O(m x n x log(m x n))、ここで m n はグリッドです寸法。

2. 空間の複雑さ:

   • 優先キューと訪問先配列のスペースは O(m x n) です。

---

実行例

入力：

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

// Example 1
$grid1 = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid1) . PHP_EOL; // Output: 7

// Example 2
$grid2 = [
    [0, 2, 4],
    [3, 2, 1],
    [1, 0, 4]
];
echo minimumTime($grid2) . PHP_EOL; // Output: -1
?>

入力：

$grid = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid); // Output: 7

このソリューションは効率的であり、制約内でうまく機能します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上がグリッド内のセルを訪問するための最小時間の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。