グリッドゲーム

2017年。グリッドゲーム

難易度: 中

トピック: 配列、行列、接頭辞の合計

サイズ 2 x n の 0 インデックス付き 2D 配列グリッドが与えられます。ここで、grid[r][c] は行列上の位置 (r, c) の点の数を表します。 2 台のロボットがこのマトリックスでゲームをプレイしています。

どちらのロボットも最初は (0, 0) から開始し、(1, n-1) に到達したいと考えています。各ロボットは、右方向 ((r, c) から (r, c 1)) または 下 ((r, c) から (r 1, c)) にのみ移動できます。

ゲームの開始時に、最初の ロボットは (0, 0) から (1, n-1) に移動し、そのパス上のセルからすべてのポイントを収集します。パス上を通過するすべてのセル (r, c) について、grid[r][c] は 0 に設定されます。その後、2 番目 ロボットは (0, 0) から (1, n-1) に移動します。 )、そのパス上のポイントを収集します。それらのパスは互いに交差する可能性があることに注意してください。

最初のロボットは、2 番目のロボットが収集するポイント数を最小限にしたいと考えています。対照的に、2 番目 ロボットは、収集するポイント数を最大化したいと考えています。両方のロボットが 最適でプレイした場合、2 番目のロボットによって収集されたポイント数を返します。

例 1:

• 入力: グリッド = [[2,5,4],[1,5,1]]
• 出力: 4
• 説明: 最初のロボットがたどる最適な経路は赤色で示され、2 番目のロボットがたどる最適な経路は青色で示されます。
  最初のロボットが訪問したセルは 0 に設定されます。
  2 番目のロボットは 0 0 4 0 = 4 ポイントを獲得します。

例 2:

• 入力: グリッド = [[3,3,1],[8,5,2]]
• 出力: 4
• 説明: 最初のロボットがたどる最適な経路は赤色で示され、2 番目のロボットがたどる最適な経路は青色で示されます。
  最初のロボットが訪問したセルは 0 に設定されます。
  2 番目のロボットは 0 3 1 0 = 4 ポイントを獲得します。

例 3:

• 入力: グリッド = [[1,3,1,15],[1,3,3,1]]
• 出力: 7
• 説明: 最初のロボットがたどる最適な経路は赤色で示され、2 番目のロボットがたどる最適な経路は青色で示されます。
  • 最初のロボットが訪問したセルは 0 に設定されます。
  • 2 番目のロボットは 0 1 3 3 0 = 7 ポイントを獲得します。

制約:

• grid.length == 2
• n == グリッド[r].length
• 1 4
• 1 5

ヒント:

1. 最初のロボットが 2 列目に移動するタイミングには n 個の選択肢があります。
2. この問題を解決するためにプレフィックス合計を使用できますか?

解決策:

次のアプローチを使用します:

1. プレフィックスの合計の計算: グリッドの両方の行のプレフィックスの合計を計算して、サブ配列の点の合計を効率的に計算します。

2. 最適な動きのシミュレーション:

   • 最初のロボットは、2 番目のロボットに残されるポイントを最小限に抑えるようにパスを決定します。
   • 各列の遷移で、最初のロボットは下に移動することを選択でき、グリッドを 2 つのセグメントに分割します。
     • 上部の残りのポイント: 遷移列の後の最上行のポイント。
     • 下位残りポイント: 遷移列の前の一番下の行にあるポイント。

3. 2 番目のロボットの最大ポイントを最小限に抑える:

   • 各遷移で、最初のロボットのパスの後に 2 番目のロボットが収集できる最大ポイントを計算します。
   • すべての遷移にわたってこれらの最大値の最小値を追跡します。

このソリューションを PHP で実装してみましょう: 2017。グリッドゲーム

<?php function gridGame($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$grid1 = [[2, 5, 4], [1, 5, 1]];
$grid2 = [[3, 3, 1], [8, 5, 2]];
$grid3 = [[1, 3, 1, 15], [1, 3, 3, 1]];

echo gridGame($grid1) . "\n"; // Output: 4
echo gridGame($grid2) . "\n"; // Output: 4
echo gridGame($grid3) . "\n"; // Output: 7
?>

説明：

1. プレフィックス合計の計算:

   • prefixTop と prefixBottom は、それぞれ上部と下部の行の累積合計を格納します。
   • これらにより、効率的な範囲合計計算が可能になります。

2. 最初のロボットのパスのシミュレーション:

   • 各列 i で、最初のロボットは列 i の後に下に移動することを決定できます。
   • これにより、グリッドが 2 つの領域に分割されます。
     • 列 i の後の最上位行 (収集ポイント: prefixTop[n] - prefixTop[i 1])。
     • 列 i の前の一番下の行 (収集されたポイント: prefixBottom[i])。

3. 2 番目のロボットの最適点:

   • 2 番目のロボットは、残り 2 つの領域の最大値を取得します。
   • すべての可能な遷移について、これらの最大値の最小値を追跡します。

4. 複雑さ:

   • 時間計算量: O(n)。プレフィックスの合計を計算し、グリッドを 1 回ループします。
   • 空間複雑度: O(n)、プレフィックス合計配列によるもの。

チュートリアルの例

入力: グリッド = [[2, 5, 4], [1, 5, 1]]

• プレフィックス合計:
  • prefixTop = [0, 2, 7, 11]
  • prefixBottom = [0, 1, 6, 7]
• 移行ポイント:
  • i = 0: 上部の残り = 11 - 7 = 9、下部の残り = 0 → 2 番目のロボット = 9.
  • i = 1: 上部の残り = 11 - 11 = 4、下部の残り = 1 → 2 番目のロボット = 4.
  • i = 2: 上部の残り = 0、下部の残り = 6 → 2 番目のロボット = 6.
• 2 番目のロボットの最小ポイント: min(9, 4, 6) = 4.

これは予想される出力と一致します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上がグリッドゲームの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。