用 Python 编写程序来查找最长矩阵路径的长度

假设我们有一个二进制矩阵，其中 0 表示空单元格，1 表示墙。我们可以从第一行的任意空单元格开始，并希望以最后一行的任意空单元格结束。我们可以向左、向右或向下移动，我们必须找到最长的路径，以便我们最多可以访问每个单元格一次。如果这不可能，则返回 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 填充
• 对于范围在 0 到 N - 1 内的 i，执行
  • ndp := 大小为 M 的列表并用 -1 填充
  • ndp2 := 大小为 M 的列表并用 -1 填充
  • 对于范围在 0 到 M - 1 内的 j，执行
    • 如果 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] := ndp[j] 和 (ndp[j - 1] + 1) 中的最大值
  • 对于 j 在 M - 2 到 0 范围内，减少 1，执行
    • 如果 matrix[i, j] 不为 1 且 ndp2[j + 1] > -1，则
      • ndp2[j] := ndp2[j] 和 (ndp2[j + 1] + 1) 的最大值
      • ndp[j] := ndp[j] 和 ndp2[j] 的最大值
  • dp := ndp
• 返回 (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 中元组列表到字典的转换
• Python - 从两个列表中配对，使得成对的元素不相同
• 使用 Python 和 SQLite 的 SQL
• 使用 pytrie 模块在 Python 中进行前缀匹配
• 创建和访问 Python 包
• 如何使用正则表达式和数据类型选择多个 DataFrame 列
• 如何在 Pandas 中查找和过滤重复行?
• 用 Python 编写程序以正确的顺序查找机场?
• 如何在 Python Pandas 中使用字典顺序切片选择数据子集?
• 用 Python 编写程序检查我们是否可以从给定的字符串字符中创建 k 个回文?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/