पायथन में शीर्ष बाएं बिंदु से नीचे दाएं बिंदु तक पहुंचने के कई तरीकों को खोजने के लिए कार्यक्रम

मान लीजिए कि हमारे पास एक एन एक्स एम बाइनरी मैट्रिक्स है। जहां 0 का मतलब खाली सेल और 1 का मतलब ब्लॉक्ड सेल है। अब ऊपरी बाएँ कोने से शुरू करते हुए, हमें नीचे दाएँ कोने तक पहुँचने के तरीकों की संख्या ज्ञात करनी होगी। अगर उत्तर बहुत बड़ा है, तो इसे 10^9 + 7 से संशोधित करें।

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

0	0	1
0	0	0
1	1	0

तो आउटपुट 2 होगा, क्योंकि नीचे दाईं ओर जाने के दो तरीके हैं:[दाएं, नीचे, दाएं, नीचे] और [नीचे, दाएं, दाएं, नीचे]।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

dp :=दिए गए मैट्रिक्स के समान आकार का एक मैट्रिक्स और 0 से भरें
dp[0, 0] :=1
मैट्रिक्स की श्रेणी 1 से पंक्ति गणना में i के लिए, करें
- यदि मैट्रिक्स [i, 0] 1 के समान है, तो
  - लूप से बाहर आएं
- अन्यथा,
  - dp[i, 0] :=1
जे के लिए श्रेणी 1 में मैट्रिक्स की कॉलम गणना के लिए, करें
- यदि मैट्रिक्स [0, j] 1 के समान है, तो
  - लूप से बाहर आएं
- अन्यथा,
  - dp[0, j] :=1
मैट्रिक्स की श्रेणी 1 से पंक्ति गणना में i के लिए, करें
- जे के लिए श्रेणी 1 में मैट्रिक्स की कॉलम गणना के लिए, करें
  - यदि मैट्रिक्स [i, j] 1 के समान है, तो
    - dp[i, j] :=0
  - अन्यथा,
    - dp[i, j] :=dp[i-1, j] + dp[i, j-1]
dp का निचला दायां मान लौटाएं

उदाहरण (पायथन)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

class Solution:
   def solve(self, matrix):
      dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
      dp[0][0] = 1
      for i in range(1, len(matrix)):
         if matrix[i][0] == 1:
            break
         else:
            dp[i][0] = 1
      for j in range(1, len(matrix[0])):
         if matrix[0][j] == 1:
            break
         else:
            dp[0][j] = 1
      for i in range(1, len(matrix)):
         for j in range(1, len(matrix[0])):
            if matrix[i][j] == 1:
               dp[i][j] = 0
            else:
               dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
      return dp[-1][-1]
ob = Solution()
matrix = [
   [0, 0, 1],
   [0, 0, 0],
   [1, 1, 0]
]
print(ob.solve(matrix))

इनपुट

matrix = [
[0, 0, 1],
[0, 0, 0],
[1, 1, 0] ]