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

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

तो, अगर इनपुट पसंद है

0	0	0	0
0	0	0	1
0	0	0	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 से एन -1 की सीमा में, करो
- ndp :=आकार M की सूची और -1 से भरें
- ndp2 :=आकार M की सूची और -1 से भरें
- जे के लिए 0 से एम -1 की सीमा में, करो
  - यदि मैट्रिक्स [i, j] 1 नहीं है और (i 0 या dp[j]> -1 के समान है), तो
    - ndp[j] :=dp[j] + 1
    - ndp2[j] :=dp[j] + 1
- जे के लिए 1 से एम -1 की सीमा में, करो
  - यदि मैट्रिक्स [i, j] 1 नहीं है और ndp[j - 1]> -1 है, तो
    - ndp[j] :=अधिकतम ndp[j] और (ndp[j - 1] + 1)
- जे के लिए एम - 2 से 0 तक, 1 से घटाएं
  - यदि मैट्रिक्स [i, j] 1 नहीं है और ndp2 [j + 1]> -1 है, तो
    - ndp2[j] :=अधिकतम ndp2[j] और (ndp2[j + 1] + 1)
    - ndp[j] :=अधिकतम ndp[j] और ndp2[j]
- डीपी:=एनडीपी
रिटर्न (अधिकतम डीपी) + 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]
]