Tìm dãy Snake dài nhất trong ma trận trong Python

Cho lưới số, tìm dãy Snake (snake sequence) và trả về. Dãy Snake: các số liền kề trong lưới, mỗi bước sang phải hoặc xuống dưới, giá trị chênh lệch ±1.

Ví dụ ma trận 4x4: 10 7 6 3 9 8 7 6 8 4 2 7 2 2 2 8 → Dãy dài nhất độ dài 6: 10(0,0)→9(1,0)→8(1,1)→7(1,2)→6(1,3)→7(2,3)→8(3,3)

Thuật toán Dynamic Programming

1. lookup[i][j] = độ dài dãy Snake dài nhất kết thúc tại (i,j).
2. Khởi tạo lookup toàn 0.
3. Duyệt ma trận, nếu ô trên hoặc trái chênh lệch 1: lookup[i][j] = max(lookup[i][j], lookup[neighbor] + 1).
4. Theo dõi ô có lookup lớn nhất.
5. Truy vết ngược từ ô đó để lấy dãy.

Ví dụ code

M = 4
N = 4

def get_path(grid, mat, i, j):
    path = []
    pt = [i, j]
    path.append(pt)
    while mat[i][j] != 0:
        if i > 0 and mat[i][j] - 1 == mat[i-1][j]:
            pt = [i-1, j]
            path.append(pt)
            i -= 1
        elif j > 0 and mat[i][j] - 1 == mat[i][j-1]:
            pt = [i, j-1]
            path.append(pt)
            j -= 1
    return path

def get_sequence(grid):
    lookup = [[0]*N for _ in range(M)]
    length_max = 0
    max_row = 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, max_col = i, 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, max_col = i, 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)

Input

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

Output

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]