在Python中编写程序以查找从左上角到右下角单元格中可以选取的硬币数并返回

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

• 空单元格为0。

• 硬币为1。

• 墙为−1。

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

因此，如果输入如下所示

0	1	1
1	1	1
−1	1	1
0	1	1

则输出将为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

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

  • 对于[(−1,0)，（0，−1）]中的每个对（dx2，dy2），
    • best：=最佳和util（i + dy1，j + dx1，k + dy2，l + dx2）的最大值
• 返回mat [i，j]+（当i与k不同时为1，否则为0）*mat [k，l]+best

• 从main方法中执行以下操作−

• 返回0和util（n−1，m−1，n−1，m−1）的最大值

让我们看下面的实现以获得更好的理解−

更多Python相关文章，请阅读：Python 教程

示例

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