मान लीजिए हमारे पास संख्याओं का एक ग्रिड है; हमें एक स्नेक अनुक्रम ढूंढना है और उसे वापस करना है। यदि एकाधिक स्नेक अनुक्रम हैं, तो केवल एक वापस करें। जैसा कि हम जानते हैं एक स्नेक अनुक्रम ग्रिड में आसन्न संख्याओं का उपयोग करके बनाया जाता है ताकि प्रत्येक संख्या के लिए, दाईं ओर की संख्या या उसके नीचे की संख्या उसके मान से या तो +1 या -1 हो। तो, यदि वर्तमान मान ग्रिड सेल (a, b) में है, तो हम या तो दाईं ओर जा सकते हैं (a, b+1) यदि वह संख्या ±1 है या नीचे जा सकते हैं (a+1, b) यदि वह संख्या ±1 है।
तो, यदि इनपुट इस तरह है
| 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)
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
एक फ़ंक्शन get_path() परिभाषित करें। यह grid, mat, i, j लेगा
path := एक नई सूची
pt := एक बिंदु [i, j]
path के अंत में pt डालें
जब grid[i, j], 0 नहीं है, करें
यदि i > 0 और grid[i, j]-1, grid[i-1, j] के समान है, तो
pt := [i-1, j]
path के अंत में pt डालें
i := i - 1
अन्यथा जब j > 0 और grid[i, j]-1, grid[i, j-1] के समान है, तो
pt := [i, j-1]
path के अंत में pt डालें
j := j - 1
path वापस करें
मुख्य विधि से, निम्नलिखित करें -
lookup := M x N आकार का एक ग्रिड बनाएं और 0 से भरें
length_max := 0, max_row := 0, max_col := 0
i के लिए 0 से M की सीमा में, करें
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
length_max प्रदर्शित करें
path := get_path(lookup, grid, max_row, max_col)
path के सभी तत्वों को उल्टे क्रम में प्रिंट करें
उदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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]
