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

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

输入

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

输出

18

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程