โปรแกรมหาความยาวของพาธเมทริกซ์ที่ยาวที่สุดใน Python

สมมติว่าเรามีเมทริกซ์ไบนารี โดยที่ 0 หมายถึงเซลล์ว่าง และ 1 หมายถึงผนัง เราสามารถเริ่มต้นที่เซลล์ว่างในแถวแรกและต้องการสิ้นสุดที่เซลล์ว่างในแถวสุดท้าย เราสามารถเลื่อนไปทางซ้าย ขวา หรือลงได้ เราต้องหาเส้นทางที่ยาวที่สุดที่เราสามารถเยี่ยมชมแต่ละเซลล์ได้พร้อมกันมากที่สุด หากไม่สามารถทำได้ ให้คืนค่า 0

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น 10 ตามที่เราสามารถย้าย (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (1, 1), (1, 2) (2, 2),(2, 1), (2, 0).

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• N :=จำนวนแถวของเมทริกซ์
• M :=จำนวนคอลัมน์ของเมทริกซ์
• dp :=รายการขนาด M และเติม -1
• สำหรับฉันในช่วง 0 ถึง N - 1 ทำ
  • ndp :=รายการขนาด M และเติม -1
  • ndp2 :=รายการขนาด M และเติม -1
  • สำหรับ j ในช่วง 0 ถึง M - 1 ทำ
    • ถ้า matrix[i, j] ไม่ใช่ 1 และ (i เหมือนกับ 0 หรือ dp[j]> -1) แล้ว
      • ndp[j] :=dp[j] + 1
      • ndp2[j] :=dp[j] + 1
  • สำหรับ j ในช่วง 1 ถึง M - 1 ทำ
    • ถ้า matrix[i, j] ไม่ใช่ 1 และ ndp[j - 1]> -1 แล้ว
      • ndp[j] :=สูงสุดของ ndp[j] และ (ndp[j - 1] + 1)
  • สำหรับ j ในช่วง M - 2 ถึง 0, ลดลง 1 ทำ
    • ถ้าเมทริกซ์[i, j] ไม่ใช่ 1 และ ndp2[j + 1]> -1 แล้ว
      • ndp2[j] :=สูงสุดของ ndp2[j] และ (ndp2[j + 1] + 1)
      • ndp[j] :=สูงสุดของ ndp[j] และ ndp2[j]
  • dp :=ndp
• ผลตอบแทน (สูงสุด dp) + 1

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(matrix):
   N = len(matrix)
   M = len(matrix[0])
   dp = [-1 for i in matrix[0]]
   for i in range(N):
      ndp = [-1 for j in matrix[0]]
      ndp2 = [-1 for j in matrix[0]]
      for j in range(M):
         if matrix[i][j] != 1 and (i == 0 or dp[j] > -1):
            ndp[j] = dp[j] + 1
            ndp2[j] = dp[j] + 1

      for j in range(1, M):
         if matrix[i][j] != 1 and ndp[j - 1] > -1:
            ndp[j] = max(ndp[j], ndp[j - 1] + 1)

      for j in range(M - 2, -1, -1):
         if matrix[i][j] != 1 and ndp2[j + 1] > -1:
            ndp2[j] = max(ndp2[j], ndp2[j + 1] + 1)
            ndp[j] = max(ndp[j], ndp2[j])

      dp = ndp
   return max(dp) + 1

matrix = [
[0, 0, 0, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
]
print(solve(matrix))

อินพุต

[
[0, 0, 0, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
]

ผลลัพธ์

10