在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)的最大值
- 对于范围0到m−1的j,进行以下操作
-
返回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