Python - Tìm đường đi dài nhất trong ma trận nhị phân

Cho ma trận nhị phân (0: ô trống, 1: tường). Bắt đầu từ bất kỳ ô trống nào hàng đầu tiên, kết thúc ở bất kỳ ô trống nào hàng cuối cùng. Di chuyển được: trái, phải, xuống. Mỗi ô chỉ thăm tối đa 1 lần. Tìm độ dài đường đi dài nhất. Trả về 0 nếu không thể.

Ví dụ

Ma trận:
0 0 0 0
0 0 0 1
0 0 0 0

Output: 10
Đường đi: (0,3)→(0,2)→(0,1)→(0,0)→(1,0)→(1,1)→(1,2)→(2,2)→(2,1)→(2,0)

Thuật toán: Quy hoạch động hàng (Row DP) với 2 lần quét

Ý tưởng: Với mỗi hàng, tính độ dài đường đi dài nhất kết thúc tại mỗi cột, xét từ hàng trước và lan sang trái/phải trong hàng hiện tại.

Trạng thái DP

• dp[j]: độ dài đường đi dài nhất đến ô (hàng trước, cột j)
• ndp[j]: độ dài đường đi đến ô (hàng hiện tại, cột j) sau khi lan sang phải
• ndp2[j]: độ dài đường đi sau khi lan sang trái

Mã Python

def solve(matrix):
    N = len(matrix)
    M = len(matrix[0])
    dp = [-1] * M
    
    for i in range(N):
        ndp = [-1] * M
        ndp2 = [-1] * M
        
        # Khởi tạo từ hàng trên
        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
        
        # Lan sang phải (left to right)
        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)
        
        # Lan sang trái (right to left)
        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 if max(dp) != -1 else 0

# Test
matrix = [
    [0, 0, 0, 0],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
]
print(solve(matrix))  # Output: 10

Phân tích độ phức tạp

• Thời gian: O(N × M) - 3 lần duyệt mỗi hàng
• Không gian: O(M) - chỉ lưu 3 mảng độ dài M

Điểm quan trọng: Hai lần quét trái→phải và phải→trái trong cùng hàng xử lý được việc đi ngang tự do trước khi xuống hàng dưới.