পাইথনে বাইনারি ম্যাট্রিক্স-এ সর্বোচ্চ পথ দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে যেখানে 0 = খালি সেল, 1 = দেয়াল। প্রথম সারি থেকে কোনো খালি সেল থেকে শুরু করে শেষ সারির কোনো খালি সেলে যেতে হবে। বাম, ডান, নিচে যাওয়া যাবে। প্রতিটি সেল hoogstens একবার দেখতে হবে। সবচেয়ে লম্বা পথের দৈর্ঘ্য বের করুন। সম্ভব না হলে 0 রিটার্ন করুন।

উদাহরণ:

0 0 0 0
0 0 0 1
0 0 0 0

সমাধানের পদ্ধতি

ডাইনামিক প্রোগ্রামিং (DP) এবং সারি-ভিত্তিক প্রক্রিয়া। প্রতিটি সারি için তিনটি অ্যারে রক্ষা করা হয়:

• dp[j]: আগের সারি থেকে সেল (i-1, j) এ পৌঁছানোর সর্বোচ্চ পথ দৈর্ঘ্য।
• ndp[j]: বাম থেকে ডান স্ক্যান করে বর্তমান সারির সর্বোচ্চ পথ।
• ndp2[j]: ডান থেকে বাম স্ক্যান করে বর্তমান সারির সর্বোচ্চ পথ।

পাইথন কোড

def solve(matrix):
    N = len(matrix)
    M = len(matrix[0])
    dp = [-1 for _ in matrix[0]]
    
    for i in range(N):
        ndp = [-1 for _ in matrix[0]]
        ndp2 = [-1 for _ 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))  # আউটপুট: 10

সময় জটিলতা

O(N × M) - প্রতিটি সেল ধ্রুবক বার প্রক্রিয়া হয়।