该程序查找可从Python的给定矩阵中收集的最大硬币数量

假设我们有一个二维矩阵，其中矩阵[r，c]代表该单元格中的硬币数量。我们可以从任何位置开始，并希望通过移动四个方向（上，下，左和右，而不是对角线）来收集硬币。当我们移至一个单元格时，将收集硬币，并且该单元格的值变为0。我们无法访问具有0个硬币的单元格，我们必须找到可以收集的最大硬币量。

所以，如果输入像

那么输出将为18，因为我们可以采用路径2-> 3-> 6-> 4-> 3

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

• 如果矩阵为空，则

• 返回0

• n：=矩阵的行数，m：=矩阵的列数

• x：=类似于[-1，1，0，0]的列表，y：=类似于[0，0，-1，1]的列表

• 定义一个功能util()。这需要a，b

• ret：= 0

• 对于0到3范围内的k，执行

• t：= mat [t1，t2]，mat [t1，t2]：= 0

• ret：= ret的最大值和（util(t1,t2)+ t）

• mat [t1，t2]：= t

• (t1,t2)：=（x [k] + a，y [k] + b）

• 如果(t1,t2)是有效单元格，则

• 返回ret

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

• res：= 0

• 对于介于0到n − 1的i

• 如果mat [i，j]为非零，则

• t：= mat [i，j]，mat [i，j]：= 0

• res：= res和（util(i, j)+ temp）的最大值

• 对于介于0到m − 1的j

• 返回资源

让我们看下面的实现以更好地理解-

示例

class Solution:
   def solve(self, mat):
      if not mat:
         return 0
      n, m = len(mat), len(mat[0])
      x, y = [−1, 1, 0, 0], [0, 0, −1, 1]
      def ok(a, b):
         return 0 <= a < n and 0 <= b < m and mat[a][b]
      def util(a, b):
         ret = 0
         for k in range(4):
            t1, t2 = x[k] + a, y[k] + b
            if ok(t1, t2):
               t, mat[t1][t2] = mat[t1][t2], 0
               ret = max(ret, util(t1, t2) + t)
               mat[t1][t2] = t
            return ret
         res = 0
         for i in range(n):
            for j in range(m):
               if mat[i][j]:
                  temp, mat[i][j] = mat[i][j], 0
                  res = max(res, util(i, j) + temp)
         return res
ob = Solution()
matrix = [
   [2, 4, 3],
   [3, 6, 0],
   [2, 0, 12]
]
print(ob.solve(matrix))

输入值

[
[2, 4, 3],
[3, 6, 0],
[2, 0, 12] ]

18