पायथन में अधिकतम लंबाई सांप अनुक्रम खोजें

मान लीजिए हमारे पास संख्याओं का एक ग्रिड है; हमें एक सांप अनुक्रम ढूंढना है और उसे वापस करना है। यदि कई साँप अनुक्रम हैं, तो केवल एक ही लौटाएँ। जैसा कि हम जानते हैं कि ग्रिड में आसन्न संख्याओं का उपयोग करके एक सांप अनुक्रम बनाया जाता है, इसलिए प्रत्येक संख्या के लिए, दाईं ओर की संख्या या उसके नीचे की संख्या या तो +1 या -1 होती है। इसलिए, यदि वर्तमान मान ग्रिड सेल (ए, बी) में है, तो हम या तो दाएं (ए, बी + 1) को स्थानांतरित कर सकते हैं यदि वह संख्या ± 1 है या नीचे जा सकती है (ए + 1, बी) यदि वह संख्या ± 1 है।

तो, अगर इनपुट पसंद है

तो आउटपुट 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

  . लेगा

• पथ:=एक नई सूची

• पीटी:=एक बिंदु [i, j]

• पथ के अंत में पीटी डालें

• जबकि ग्रिड [i, j] 0 नहीं है, करें

  • अगर i> 0 और ग्रिड [i, j]-1 ग्रिड [i-1, j] के समान है, तो

    • पीटी:=[आई-1, जे]

    • पथ के अंत में पीटी डालें

    • मैं :=मैं - 1

  • अन्यथा जब j> 0 और ग्रिड[i, j]-1 ग्रिड [i, j-1] के समान है, तब

    • पीटी:=[मैं, जे-1]

    • पथ के अंत में पीटी डालें

    • जे:=जे - 1

• वापसी पथ

• मुख्य विधि से, निम्न कार्य करें -

• लुकअप :=आकार M x N का ग्रिड बनाएं और 0 से भरें

• length_max :=0, max_row :=0, max_col :=0

• मैं के लिए 0 से एम की सीमा में, करो

  • j के लिए 0 से N की सीमा में, करें

    • अगर i या j गैर-शून्य है, तो

      • अगर (i> 0 an और |grid[i-1, j] - grid[i, j]| 1 है तो

        • लुकअप[i,j] =अधिकतम लुकअप[i,j],लुकअप[i-1,j] + 1)

        • अगर length_max <लुकअप[i,j], तो

          • length_max :=लुकअप[i, j]

          • max_row :=i

          • max_col :=j

      • अगर (j> 0 और |grid[i, j-1] - grid[i, j]| 1 है तो

        • अगर length_max <लुकअप[i][j] शून्य नहीं है, तो

        • लुकअप[i,j] =अधिकतम लुकअप[i,j],लुकअप[i,j-1] + 1)

          • length_max :=लुकअप[i, j]

          • max_row :=i

          • max_col :=j

• लंबाई_मैक्स प्रदर्शित करें

• पथ:=get_path (लुकअप, ग्रिड, 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("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]