在 Python 中查找最大长度的蛇形序列

pythonserver side programmingprogramming更新于 2025/10/10 16:12:17

假设我们有一个数字网格;我们必须找到一个蛇形序列并返回它。如果有多个蛇形序列,则只返回一个。众所周知,蛇形序列是使用网格中的相邻数字组成的,因此对于每个数字,右侧的数字或其下方的数字是其值的 +1 或 -1。因此,如果当前值在网格单元格 (a, b) 中,如果该数字为 ± 1,我们可以向右移动 (a, b+1),或者如果该数字为 ± 则向下移动 (a+1, b) 1.

因此,如果输入如下

10763
9876
8427
2228

则输出为 6,序列 − 10 (0, 0) 到 9 (1, 0) 到 8 (1, 1) 到 7 (1, 2) 到 6 (1, 3) 到 7 (2, 3) 到 8 (3, 3)

为了解决这个问题,我们将遵循以下步骤 −

  • 定义一个函数 get_path() 。这将需要 grid、mat、i、j

  • path := 一个新列表

  • pt := 一个点 [i, j]

  • 在路径末尾插入 pt

  • 当 grid[i, j] 不为 0 时,执行

    • 如果 i > 0 且 grid[i, j]-1 与 grid[i-1, j] 相同,则

      • pt := [i-1, j]

      • 在路径末尾插入 pt

      • i := i - 1

    • 否则当 j > 0 且 grid[i, j]-1 与 grid[i, j-1] 相同,则

      • pt := [i, j-1]

      • 在路径末尾插入 pt

      • j := j - 1

  • 返回路径

  • 从主方法中,执行以下操作 −

  • lookup := 制作一个大小为 M x N 的网格并用 0 填充

  • length_max := 0, max_row := 0, max_col := 0

  • 对于范围为 0 到 M 的 i,执行

    • 对于 j 在 0 到 N 范围内的情况,执行

      • 如果 i 或 j 非零,则

        • 如果 (i > 0 并且 |grid[i-1, j] - grid[i, j]| 为 1,则

          • lookup[i,j] = lookup[i,j],lookup[i-1,j] + 1 中的最大值

          • 如果 length_max < lookup[i,j],则

            • length_max := lookup[i, j]

            • max_row := i

            • max_col := j

        • 如果 (j > 0 且 |grid[i, j-1] - grid[i, j]| 为 1,则

          • 如果 length_max < lookup[i][j] 非零,则

          • lookup[i,j] = lookup[i,j],lookup[i,j-1] + 1 中的最大值)

            • length_max := lookup[i, j]

            • max_row := i

            • max_col := j

  • display length_max

  • path := get_path(lookup, grid, max_row, max_col)

  • 以相反的顺序打印路径中的所有元素

示例

让我们看看下面的实现以便更好地理解 &mius;

M = 4
N = 4
def get_path(grid, mat, i, j):
   path = list()
   pt = [i, j]
   path.append(pt)
   while (grid[i][j] != 0):
      if (i > 0 and grid[i][j]-1 == grid[i-1][j]):
         pt = [i-1, j]
         path.append(pt)
         i -= 1
      elif (j > 0 and grid[i][j]-1 == grid[i][j-1]):
         pt = [i, j-1]
         path.append(pt)
         j -= 1
   return path
def get_sequence(grid):
   lookup = [[0 for i in range(N)] for j in range(M)]
   length_max = 0
   max_row = 0
   max_col = 0
   for i in range(M):
      for j in range(N):
         if (i or j):
            if (i > 0 and
               abs(grid[i-1][j] - grid[i][j]) == 1):
                  lookup[i][j] = max(lookup[i][j],lookup[i-1][j] + 1)
                  if (length_max < lookup[i][j]):
                     length_max = lookup[i][j]
                     max_row = i
                     max_col = j
                  if (j > 0 and
                     abs(grid[i][j-1] - grid[i][j]) == 1):
                     lookup[i][j] = max(lookup[i][j],lookup[i][j-1] + 1)
                     if (length_max < lookup[i][j]):
                        length_max = lookup[i][j]
                        max_row = i
                        max_col = j
   print("Maximum length:", length_max)
   path = get_path(lookup, grid, max_row, max_col)
   print("Sequence is:")
   for ele in reversed(path):
   print(grid[ele[0]][ele[1]], " [", ele[0], ", ", ele[1], "]", sep = "")
grid = [
   [10, 7, 6, 3],
   [9, 8, 7, 6],
   [8, 4, 2, 7],
   [2, 2, 2, 8]]
get_sequence(grid)

输入

[[10, 7, 6, 3],
[9, 8, 7, 6],
[8, 4, 2, 7],
[2, 2, 2, 8]]

输出

Maximum length: 6
Sequence is:
10 [0, 0]
9 [1, 0]
8 [1, 1]
7 [1, 2]
6 [1, 3]
7 [2, 3]
8 [3, 3]

相关文章


有用资源