Python - หาความยาวเส้นทางที่ยาวที่สุดในเมทริกซ์ไบนารี

โจทย์: กำหนดให้มีเมทริกซ์ไบนารี (0 = ช่องว่าง, 1 = กำแพง) เริ่มจากช่องว่างแถวแรก ต้องไปถึงช่องว่างแถวสุดท้าย สามารถเคลื่อนที่ซ้าย ขวา ล่าง ได้ ต้องการหาเส้นทางที่ยาวที่สุดที่ไม่ซ้ำช่อง (Visit each cell at most once) หากไม่สามารถไปถึงได้ คืนค่า 0

ตัวอย่าง

Matrix:
0 0 0 0
0 0 0 1
0 0 0 0

Output: 10
เส้นทาง: (0,3)→(0,2)→(0,1)→(0,0)→(1,0)→(1,1)→(1,2)→(2,2)→(2,1)→(2,0) รวม 10 ช่อง

อัลกอริทึม: Dynamic Programming แบบแถวต่อแถว (Row-by-row DP)

เนื่องจากเคลื่อนที่ได้เฉพาะ ซ้าย ขวา ล่าง (ไม่ขึ้น) จึงสามารถประมวลผลแถวต่อแถวได้

ขั้นตอนการทำงาน

1. dp[j] = ความยาวเส้นทางสูงสุดที่สิ้นสุดที่คอลัมน์ j ของแถวปัจจุบัน
2. สำหรับแต่ละแถว สร้าง ndp (Left-to-right pass) และ ndp2 (Right-to-left pass)
3. Left-to-right: เลื่อนจากซ้ายไปขวา อัปเดต ndp[j] = max(ndp[j], ndp[j-1] + 1)
4. Right-to-left: เลื่อนจากขวาไปซ้าย อัปเดต ndp2[j] = max(ndp2[j], ndp2[j+1] + 1) และรวมกับ ndp
5. อัปเดต dp = ndp สำหรับแถวถัดไป

โค้ด Python

def solve(matrix):
    N = len(matrix)
    M = len(matrix[0])
    dp = [-1 for _ in matrix[0]]  # เริ่มต้น -1 (ไม่สามารถถึงได้)
    
    for i in range(N):
        ndp = [-1 for _ in matrix[0]]
        ndp2 = [-1 for _ in matrix[0]]
        
        # เริ่มต้นจากด้านบน (Down move)
        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
        
        # Left-to-right pass (เคลื่อนที่ขวา)
        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)
        
        # Right-to-left pass (เคลื่อนที่ซ้าย)
        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))  # Output: 10

ความซับซ้อน

• Time Complexity: O(N × M) - ประมวลผลแต่ละเซลล์คงที่ครั้ง
• Space Complexity: O(M) - เก็บแค่ 2 แถว DP

รายละเอียดเพิ่มเติม

• ndp เก็บค่าที่ได้จากการเคลื่อนที่จากซ้ายไปขวา
• ndp2 เก็บค่าที่ได้จากการเคลื่อนที่จากขวาไปซ้าย
• การรวม ndp[j] = max(ndp[j], ndp2[j]) ให้ค่าที่ดีที่สุดจากทั้งสองทิศทาง
• คืนค่า max(dp) + 1 เพราะ dp นับ "ขั้นตอน" (Edges) แต่โจทย์ถาม "จำนวนโหนด" (Nodes = Edges + 1)