網格遊戲

2017 年。網格遊戲

難度：中

主題：陣列、矩陣、前綴和

給定一個 0 索引 大小為 2 x n 的二維陣列網格，其中 grid[r][c] 表示矩陣上位置 (r, c) 處的點數。兩個機器人正在這個矩陣上玩遊戲。

兩個機器人最初都從 (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。然後，第二個 機器人從 (0, 0) 移動到 (1, n-1) ），收集其路徑上的點。請注意，它們的路徑可能會相互交叉。

第一個機器人想要最小化第二個機器人收集的點數。相較之下，第二個機器人想要最大化它收集的點數。如果兩個機器人都表現最佳，則回傳第二個機器人收集的分數。

範例1：

• 輸入： grid = [[2,5,4],[1,5,1]]
• 輸出： 4
• 說明：第一個機器人所採取的最佳路徑以紅色顯示，第二個機器人所採取的最佳路徑以藍色顯示。
  第一個機器人存取的單元格設定為 0。
  第二個機器人將收集 0 0 4 0 = 4 分。

範例2：

• 輸入： grid = [[3,3,1],[8,5,2]]
• 輸出： 4
• 說明：第一個機器人所採取的最佳路徑以紅色顯示，第二個機器人所採取的最佳路徑以藍色顯示。
  第一個機器人存取的單元格設定為 0。
  第二個機器人將收集 0 3 1 0 = 4 分。

範例 3：

• 輸入： grid = [[1,3,1,15],[1,3,3,1]]
• 輸出： 7
• 說明：第一個機器人所採取的最佳路徑以紅色顯示，第二個機器人所採取的最佳路徑以藍色顯示。
  • 第一個機器人存取的單元格設定為 0。
  • 第二個機器人將收集 0 1 3 3 0 = 7 分。

約束：

• grid.length == 2
• n == grid[r].length
• 1 4
• 1 5

提示：

1. 第一個機器人移動到第二排時有n種選擇。
2. 我們可以使用前綴和來幫助解決這個問題嗎？

解：

我們將使用以下方法：

1. 前綴和計算：我們將計算網格兩行的前綴和，以有效計算任何子數組的點總和。

2. 模擬最佳運動:

   • 第一個機器人決定其路徑，以最小化留給第二個機器人的點。
   • 在每個列轉換時，第一個機器人可以選擇向下移動，將網格分成兩部分：
     • 上部剩餘點：過渡列之後頂行的點。
     • 較低剩餘點：過渡列之前的底行中的點。

3. 最小化第二個機器人的最大分數:

   • 在每次轉換時，計算第二個機器人在第一個機器人的路徑之後可以收集的最大點數。
   • 追蹤所有轉換中這些最大值的最小值。

讓我們用 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 列之後向下移動。
   • 這將網格分為兩個區域：
     • 第 i 列之後的頂行（收集點：prefixTop[n] - prefixTop[i 1]）。
     • 第 i 列之前的底行（收集點：prefixBottom[i]）。

3. 第二個機器人的最優點:

   • 第二個機器人將佔據剩餘兩個區域中的最大值。
   • 我們追蹤所有可能的轉換的最大值中的最小值。

4. 複雜性：

   • 時間複雜度：O(n)，因為我們計算前綴和並循環遍歷網格一次。
   • 空間複雜度：O(n)，由於前綴和陣列。

範例演練

輸入：網格 = [[2, 5, 4], [1, 5, 1]]

• 前綴和：
  • 字首頂部 = [0, 2, 7, 11]
  • prefixBottom = [0, 1, 6, 7]
• 過渡點：
  • i = 0：頂部剩餘= 11 - 7 = 9，底部剩餘= 00 → 第二個機器人 = 9
  .
  • i = 1：頂部剩餘= 11 - 11 = 4，底部剩餘= 11 → 第二個機器人 = 4
  • . i = 2：頂部剩餘= 0，底部剩餘= 6 → → →
  →
  →
→
• → → → → → → →
→

→

→

→

→ → →第二個機器人=

6.

• 第二個機器人的最低分數:
min(9, 4, 6) = 4
• .

這與預期輸出相符。 聯絡連結 如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！ 如果您想要更多類似的有用內容，請隨時關注我： 領英 GitHub

以上是網格遊戲的詳細內容。更多資訊請關注PHP中文網其他相關文章！