পাইথনে সর্বোচ্চ দৈর্ঘ্যের স্নেক সিকোয়েন্স বের করা

ধরা যাক একটি সংখ্যার গ্রিড (grid) আছে। আমাদের একটি স্নেক সিকোয়েন্স বের করতে হবে। স্নেক সিকোয়েন্স মানে প্রতিটি সংখ্যার ডানদিক বা নিচের সংখ্যা তার সাথে ±1 পার্থক্য রাখে। যদি একাধিক সিকোয়েন্স থাকে তবে যেকোনো একটি রিটার্ন করুন।

ইনপুট গ্রিড: 10 7 6 3 9 8 7 6 8 4 2 7 2 2 2 8 আউটপুট: দৈর্ঘ্য ৬, সিকোয়েন্স: 10(0,0) → 9(1,0) → 8(1,1) → 7(1,2) → 6(1,3) → 7(2,3) → 8(3,3)

সমাধানের ধাপসমূহ (DP + পাথ রিকভারি)

• lookup[M][N] DP টেবিল 0 দিয়ে ইনিশিয়ালাইজ
• প্রতিটি সেল (i,j) এর জন্য উপরে এবং বামের সেল চেক করুন ±1 পার্থক্য থাকলে lookup আপডেট করুন
• সর্বোচ্চ দৈর্ঘ্য এবং তার অবস্থান (max_row, max_col) ট্র্যাক করুন
• get_path ফাংশন দিয়ে লুকআপ টেবিল থেকে পাথ রিকভার করুন

উদাহরণ

M = 4; N = 4
def get_path(grid, mat, i, j):
    path = []
    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]*N for _ in range(M)]
    length_max = 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 = 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]