ค้นหาลำดับงูที่มีความยาวสูงสุดใน Python

สมมติว่าเรามีตารางตัวเลข เราต้องหาลำดับงูและส่งคืน หากมีลำดับของงูหลายชุด ให้ส่งคืนชุดเดียว อย่างที่เราทราบกันดีว่าลำดับของงูถูกสร้างขึ้นโดยใช้ตัวเลขที่อยู่ติดกันในตาราง ดังนั้นสำหรับตัวเลขแต่ละตัว ตัวเลขทางด้านขวามือหรือตัวเลขด้านล่างจะเป็น +1 หรือ -1 ค่าของมัน ดังนั้น หากค่าปัจจุบันอยู่ในเซลล์กริด (a, b) เราสามารถเลื่อนไปทางขวา (a, b+1) ถ้าตัวเลขนั้นเป็น ± 1 หรือย้ายไปที่ด้านล่าง (a+1, b) ถ้าตัวเลขนั้นเป็น ± 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() นี่จะใช้กริด, เสื่อ, ฉัน, เจ

• เส้นทาง :=รายการใหม่

• pt :=จุด [i, j]

• แทรก pt ที่ส่วนท้ายของเส้นทาง

• ในขณะที่ grid[i, j] ไม่ใช่ 0, do

  • ถ้า i> 0 และ grid[i, j]-1 เหมือนกับ grid[i-1, j] แล้ว

    • pt :=[i-1, j]

    • แทรก pt ที่ส่วนท้ายของเส้นทาง

    • ผม :=ผม - 1

  • มิฉะนั้น เมื่อ j> 0 และ grid[i, j]-1 เหมือนกับ grid[i, j-1] แล้ว

    • pt :=[i, j-1]

    • แทรก pt ที่ส่วนท้ายของเส้นทาง

    • เจ :=เจ - 1

• เส้นทางกลับ

• จากวิธีหลัก ให้ทำดังนี้ −

• ค้นหา :=สร้างตารางขนาด M x N และเติมด้วย 0

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

• สำหรับผมอยู่ในช่วง 0 ถึง M ทำ

  • สำหรับ j ในช่วง 0 ถึง N ให้ทำ

    • ถ้า i หรือ j ไม่ใช่ศูนย์ แล้ว

      • ถ้า (i> 0 an และ |grid[i-1, j] - grid[i, j]| คือ 1 แล้ว

        • lookup[i,j] =ค่าสูงสุดของการค้นหา[i,j],lookup[i-1,j] + 1)

        • ถ้า length_max

          • length_max :=ค้นหา[i, j]

          • max_row :=ผม

          • max_col :=เจ

      • ถ้า (j> 0 และ |grid[i, j-1] - grid[i, j]| คือ 1 แล้ว

        • ถ้า length_max

        • lookup[i,j] =ค่าสูงสุดของการค้นหา[i,j],lookup[i,j-1] + 1)

          • length_max :=ค้นหา[i, j]

          • max_row :=ผม

          • max_col :=เจ

• จอแสดงผล length_max

• เส้นทาง :=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]