程序查找可从左上角到右下角单元中挑选的硬币数量并返回Python
假设我们有一个带有3个可能值的2D矩阵-
空单元为0。
1硬币。
-1为墙。
我们必须找到硬币的最大数量，方法是从左上角的单元格开始，然后仅向右或向下移动，到达右下角的单元格。然后通过仅向上或向左移动回到左上角的单元格。当我们拿起硬币时，单元格值变为0。如果我们无法到达右下角的单元格，则返回0。
所以，如果输入像
那么输出将是8。
为了解决这个问题，我们将遵循以下步骤-
n：=垫子的行数，m：=垫子的列数
定义一个功能util()。这需要i，j，k，l
如果i和j不在mat的范围内，或者mat[i，j]等于-1，则
返回-inf
如果k和l不在mat的范围内，或者mat[k，l]等于-1，则
返回-inf
如果i，j，k和l均为0，则
返回垫[0，0]
最好：=-inf
对于[[−-1，0），（0，−1）]中的每对(dx1,dy1)，执行
best：=best和util（i+dy1，j+dx1，k+dy2，l+dx2）的最大值
对于[[−-1，0），（0，−1）]中的每对(dx2,dy2)，
返回mat[i，j]+（当i与k不相同时为1，否则为0）*mat[k，l]+最佳
从主要方法中执行以下操作-
返回最大值0和util(n-1,m-1,n-1,m-1)
让我们看下面的实现以更好地理解-
示例
class Solution:
def solve(self, mat):
n, m = len(mat), len(mat[0])
def util(i, j, k, l):
if not (0 <= i < n and 0 <= j < m) or mat[i][j] == −1:
return −1e9
if not (0 <= k < n and 0 <= l < m) or mat[k][l] == −1:
return −1e9
if i == 0 and j == 0 and k == 0 and l == 0:
return mat[0][0]
best = −1e9
for dx1, dy1 in [(−1, 0), (0, −1)]:
for dx2, dy2 in [(−1, 0), (0, −1)]:
best = max(best, util(i + dy1, j + dx1, k + dy2, l + dx2))
return mat[i][j] + (i != k) * mat[k][l] + best
return max(0, util(n − 1, m − 1, n − 1, m − 1))
ob = Solution()
matrix = [
[0, 1, 1],
[1, 1, 1],
[1, −1, 1],
[0, 1, 1]
]
print(ob.solve(matrix))输入值
[ [0, 1, 1], [1, 1, 1], [1, −1, 1], [0, 1, 1] ]输出结果
8