在Python中找到最大长度的Snake序列

  • Z时代
  • 2024-01-10
  • 分类：综合

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

所以，如果输入像

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()。这将需要网格，垫子，i，j

  • 路径：=一个新列表

  • pt：=点[i，j]

  • 在路径末尾插入pt

  • 当grid [i，j]不为0时

    • pt：= [i，j-1]

    • 在路径末尾插入pt

    • j：= j-1

    • pt：= [i-1，j]

    • 在路径末尾插入pt

    • 我：=我-1

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

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

    • 返回路径

    • 从主要方法中，执行以下操作-

    • 查找：=制作一个大小为M x N的网格并填充0

    • length_max：= 0，max_row：= 0，max_col：= 0

    • 对于0到M范围内的i，执行

      • 如果i或j不为零，则

      • 如果length_max <lookup [i] [j]不为零，则

      • lookup [i，j] = lookup [i，j]，lookup [i，j-1]的最大值+ 1）

      • length_max：=查找[i，j]

      • max_row：=我

      • max_col：= j

      • lookup [i，j] = lookup [i，j]，lookup [i-1，j]的最大值+ 1）

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

      • length_max：=查找[i，j]

      • max_row：=我

      • max_col：= j

      • 如果（i> 0 an并且| grid [i-1，j]-grid [i，j] |为1，则

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

      • 对于0到N范围内的j，执行

      • 显示length_max

      • 路径：= 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("最大长度：", length_max)
         path = get_path(lookup, grid, max_row, max_col)
         print("顺序是：")
         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]]

      输出结果

      最大长度： 6
      顺序是：
      10 [0, 0]
      9 [1, 0]
      8 [1, 1]
      7 [1, 2]
      6 [1, 3]
      7 [2, 3]
      8 [3, 3]

      以上是 在Python中找到最大长度的Snake序列 的全部内容， 来源链接： utcz.com/z/334755.html

      回到顶部