该程序查找可从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，执行
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
以上是 该程序查找可从Python的给定矩阵中收集的最大硬币数量 的全部内容， 来源链接： utcz.com/z/351370.html
