在Python中找到最大长度的Snake序列
假设我们有一个数字网格；我们必须找到一条蛇序列并将其返回。如果有多个蛇序列，则仅返回一个。众所周知，蛇序列是使用网格中的相邻数字构成的，因此对于每个数字，右侧的数字或下方的数字为其值的+1或-1。因此，如果当前值在网格单元格(a,b)中，则如果该数字为±1，则可以向右移动（a，b+1）；如果该数字为±1，则可以移至下方（a+1，b）。
所以，如果输入像
那么输出将为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]相同时，则
返回路径
从主要方法中，执行以下操作-
查找：=制作一个大小为MxN的网格并填充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>0an并且|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]