在Python中找到给定矩阵中可以收集的最大硬币金额的程序

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

所以，如果输入如下：

2	4	3
3	6	0
2	0	12

那么输出将是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，进行以下操作
- (t1，t2):=(x [k]+a，y [k]+b)
- 如果（t1，t2）是有效单元格，则
  - t:=mat[t1，t2]，mat[t1，t2]:=0
  - ret:=ret和(util(t1，t2)+t)的最大值
  - mat[t1，t2]:=t
返回ret
从主方法做以下操作
res:=0
对于范围0到n−1的i，进行以下操作
- 对于范围0到m−1的j，进行以下操作
  - 如果mat[i，j]为非零，则
  - t:=mat[i，j]，mat[i，j]:=0
  - res:=res和(util(i，j)+temp)的最大值
返回res

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

例子

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))