程序查找可从左上角到右下角单元中挑选的硬币数量并返回Python

假设我们有一个带有3个可能值的2D矩阵-

• 空单元为0。

• 1硬币。

• -1为墙。

我们必须找到硬币的最大数量，方法是从左上角的单元格开始，然后仅向右或向下移动，到达右下角的单元格。然后通过仅向上或向左移动回到左上角的单元格。当我们拿起硬币时，单元格值变为0。如果我们无法到达右下角的单元格，则返回0。

所以，如果输入像

那么输出将是8。

为了解决这个问题，我们将遵循以下步骤-

• n：=垫子的行数，m：=垫子的列数

• 定义一个功能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，则

• 返回垫[0，0]

• 最好：= -inf

• 对于[[−-1，0），（0，−1）]中的每对(dx1,dy1)，执行

• best：= best和util（i + dy1，j + dx1，k + dy2，l + dx2）的最大值

• 对于[[−-1，0），（0，−1）]中的每对(dx2,dy2)，

• 返回mat [i，j] +（当i与k不相同时为1，否则为0）* mat [k，l] +最佳

• 从主要方法中执行以下操作-

• 返回最大值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