Python程式：找出可從左上角拾取到右下角單元格的硬幣數量

假設我們有一個二維矩陣，其中有3個可能的值：

  • 0 代表空單元格。

  • 1 代表一枚硬幣。

  • -1 代表一堵牆。

我們必須找到從左上角單元格開始，只能向右或向下移動到達右下角單元格，然後只能向上或向左移動返回左上角單元格，可以拾取的最大硬幣數量。如果無法到達右下角單元格，則返回0。拾取硬幣後，單元格值變為0。

例如，如果輸入如下：

011
111
-111
011

則輸出為8。

為了解決這個問題，我們將遵循以下步驟：

  • n := mat的行數，m := mat的列數

  • 定義一個函式 util()。它將接收 i, j, k, l 作為引數。

  • 如果 i 和 j 超出 mat 的範圍，或者 mat[i, j] 等於 -1，則

    • 返回 -inf（負無窮大）

  • 如果 k 和 l 超出 mat 的範圍，或者 mat[k, l] 等於 -1，則

    • 返回 -inf（負無窮大）

  • 如果 i, j, k 和 l 全部為 0，則

    • 返回 mat[0, 0]

  • best := -inf（負無窮大）

  • 對於每個 (dx1, dy1) 對 in [(−1, 0) ,(0, −1) ]，執行：

    • 對於每個 (dx2, dy2) 對 in [(−1, 0) ,(0, −1) ]，執行：

      • best := best 和 util(i + dy1, j + dx1, k + dy2, l + dx2) 的最大值

  • 返回 mat[i, j] + (當 i 不等於 k 時為 1，否則為 0) * mat[k, l] + best

  • 在主方法中執行以下操作：

  • 返回 0 和 util(n − 1, m − 1, n − 1, m − 1) 的最大值

讓我們看下面的實現來更好地理解：

示例

線上演示

class Solution:
   def solve(self, mat):
      n, m = len(mat), len(mat[0])
      def util(i, j, k, l):
         if not (0 <= i < n and 0 <= j < m) or mat[i][j] == −1:
            return −1e9
         if not (0 <= k < n and 0 <= l < m) or mat[k][l] == −1:
            return −1e9
         if i == 0 and j == 0 and k == 0 and l == 0:
            return mat[0][0]
         best = −1e9
         for dx1, dy1 in [(−1, 0), (0, −1)]:
            for dx2, dy2 in [(−1, 0), (0, −1)]:
               best = max(best, util(i + dy1, j + dx1, k + dy2, l + dx2))
         return mat[i][j] + (i != k) * mat[k][l] + best
      return max(0, util(n − 1, m − 1, n − 1, m − 1))
ob = Solution()
matrix = [
   [0, 1, 1],
   [1, 1, 1],
   [1, −1, 1],
   [0, 1, 1]
]
print(ob.solve(matrix))

輸入

[
   [0, 1, 1],
   [1, 1, 1],
   [1, −1, 1],
   [0, 1, 1]
]

輸出

8

更新於：2020-12-26

瀏覽量：104

啟動你的職業生涯

完成課程獲得認證

開始學習
廣告