पायथन में टॉप-लेफ्ट से बॉटम-राइट तक पहुंचने के तरीकों की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास एक N x M बाइनरी मैट्रिक्स है। जहां 0 का अर्थ खाली सेल है और 1 का अर्थ ब्लॉक्ड सेल है। अब टॉप-लेफ्ट कॉर्नर से शुरू करके, हमें बॉटम-राइट कॉर्नर तक पहुंचने के तरीकों की संख्या ढूंढनी है। यदि उत्तर बहुत बड़ा है, तो इसे 10^9 + 7 से मॉड करें।

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

0	0	1
0	0	0
1	1	0

तो आउटपुट 2 होगा, क्योंकि बॉटम-राइट तक पहुंचने के दो तरीके हैं: [Right, Down, Right, Down] और [Down, Right, Right, Down]।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम डायनामिक प्रोग्रामिंग का उपयोग करेंगे:

dp := दिए गए मैट्रिक्स के आकार का मैट्रिक्स, 0 से भरा हुआ
dp[0][0] := 1
i को 1 से पंक्तियों की संख्या - 1 तक लूप चलाएं:
- यदि matrix[i][0] == 1 है, तो लूप तोड़ें
- अन्यथा, dp[i][0] := 1
j को 1 से कॉलम की संख्या - 1 तक लूप चलाएं:
- यदि matrix[0][j] == 1 है, तो लूप तोड़ें
- अन्यथा, dp[0][j] := 1
i को 1 से पंक्तियों - 1 तक, j को 1 से कॉलम - 1 तक लूप चलाएं:
- यदि matrix[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] ]