Python 中寻找最长矩阵路径的长度的程序

Python 中寻找最长矩阵路径的长度的程序

假设我们有一个二进制矩阵,其中 0 表示空单元格,1 表示墙壁。我们可以从第一行的任意空单元格开始,并想在最后一行的任意空单元格结束。我们可以向左、向右或向下移动,我们必须找到这样的最长路径,该路径可以最多访问每个单元格一次。如果这不可能,则返回 0。

因此,如果输入如下所示:

0 0 0 0
0 0 0 1
0 0 0 0

那么输出将为 10,因为我们可以移动 (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (2, 1), (2, 0)。

为解决此问题,我们将遵循以下步骤:

  • N:矩阵的行数
  • M:矩阵的列数
  • dp:一个大小为 M 的列表,填充为 -1
  • 对于 i 在 0 到 N – 1 的范围内,
    • ndp:大小为 M 的列表,并用 -1 填充
    • ndp2:大小为 M 的列表,并用 -1 填充
    • 对于 j 在 0 到 M – 1 的范围内,
      • 如果 matrix[i, j] 不是 1 并且 (i 与 0 相同或 dp[j] > -1),则
      • ndp[j] = dp[j] + 1
      • ndp2[j] = dp[j] + 1
    • 对于 j 在 1 到 M – 1 的范围内,
      • 如果 matrix[i, j] 不是 1 并且 ndp[j – 1] > -1,则
      • ndp[j] = max(ndp[j], (ndp[j – 1] + 1))
    • 对于 j 在 M – 2 到 0 的范围内,递减 1,
      • 如果 matrix[i, j] 不是 1 并且 ndp2[j + 1] > -1,则
      • ndp2[j] = max(ndp2[j], (ndp2[j + 1] + 1))
      • ndp[j] = max(ndp[j], ndp2[j])
    • dp = ndp
  • 返回 max(dp) + 1

例子

让我们看一下以下实现,以获得更好的理解 –

def solve(matrix):
   N = len(matrix)
   M = len(matrix[0])
   dp = [-1 for i in matrix[0]]
   for i in range(N):
      ndp = [-1 for j in matrix[0]]
      ndp2 = [-1 for j in matrix[0]]
      for j in range(M):
         if matrix[i][j] != 1 and (i == 0 or dp[j] > -1):
            ndp[j] = dp[j] + 1
            ndp2[j] = dp[j] + 1

      for j in range(1, M):
         if matrix[i][j] != 1 and ndp[j - 1] > -1:
            ndp[j] = max(ndp[j], ndp[j - 1] + 1)

      for j in range(M - 2, -1, -1):
         if matrix[i][j] != 1 and ndp2[j + 1] > -1:
            ndp2[j] = max(ndp2[j], ndp2[j + 1] + 1)
            ndp[j] = max(ndp[j], ndp2[j])

      dp = ndp
   return max(dp) + 1

matrix = [
[0, 0, 0, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
]
print(solve(matrix))

输入

[
[0, 0, 0, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
]

输出

10

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程