पायथन में मैट्रिक्स में सबसे लंबे पथ की लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है, जहां 0 खाली सेल दर्शाता है और 1 दीवार दर्शाता है। हम पहली पंक्ति के किसी भी खाली सेल से शुरू कर सकते हैं और अंतिम पंक्ति के किसी भी खाली सेल पर समाप्त करना चाहते हैं। हम बाएं, दाएं या नीचे जा सकते हैं, हमें सबसे लंबा ऐसा पथ ढूंढना है जहां हम प्रत्येक सेल को अधिकतम एक बार देख सकें। यदि यह संभव नहीं है, तो 0 लौटाएं।

उदाहरण के लिए, यदि इनपुट है:

तो आउटपुट 10 होगा, क्योंकि हम इस तरह जा सकते हैं: (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (2, 1), (2, 0)।

एल्गोरिदम

1. N := मैट्रिक्स की पंक्ति संख्या
2. M := मैट्रिक्स की कॉलम संख्या
3. dp := आकार M की सूची, -1 से भरी हुई
4. प्रत्येक पंक्ति i के लिए 0 से N-1 तक:
   • ndp और ndp2 को -1 से भरी सूचियों के रूप में आरंभ करें
   • बाएं से दाएं पास: ndp को अपडेट करें
   • दाएं से बाएं पास: ndp2 को अपडेट करें और ndp के साथ मर्ज करें
   • dp := ndp
5. max(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))  # आउटपुट: 10

इनपुट

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

आउटपुट

10