该程序查找可从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