पायथन में शुरुआत से अंत तक लागत k वाले पथों की संख्या गिनने का प्रोग्राम

मान लीजिए हमारे पास एक 2D बाइनरी मैट्रिक्स और एक मान k है। ऊपरी-बाएं सेल से शुरू करके, हमें नीचे-दाएं सेल तक जाना है। एक चरण में हम केवल नीचे या दाएं जा सकते हैं। एक पथ का स्कोर पथ पर सेल्स के मानों का योग है। हमें शुरुआती सेल से अंतिम सेल तक स्कोर k वाले पथों की संख्या ज्ञात करनी है। यदि तरीके बहुत अधिक हैं तो परिणाम 10^9+7 से मॉड्यूलो वापस करें।

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

एल्गोरिदम (रिकर्सिव DFS)

• deno := 10^9 + 7
• m := पंक्तियों की संख्या, n := कॉलम की संख्या
• dfs(i, j, pts) फ़ंक्शन परिभाषित करें:
  • यदि i >= m या j >= n, तो 0 वापस करें
  • pts += matrix[i][j]
  • यदि i == m-1 और j == n-1, तो 1 यदि pts == k अन्यथा 0 वापस करें
  • dfs(i+1, j, pts) + dfs(i, j+1, pts) वापस करें
• मुख्य विधि से dfs(0, 0, 0) % deno वापस करें

उदाहरण

class Solution:
    def solve(self, matrix, k):
        m, n = len(matrix), len(matrix[0])
        def dfs(i=0, j=0, pts=0):
            if i >= m or j >= n: return 0
            pts += matrix[i][j]
            if i == m - 1 and j == n - 1:
                return int(pts == k)
            return dfs(i + 1, j, pts) + dfs(i, j + 1, pts)
        return dfs() % (10**9 + 7)

ob = Solution()
matrix = [[0, 0, 1], [1, 0, 1], [0, 1, 0]]
k = 2
print(ob.solve(matrix, k))

इनपुट

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

आउटपुट

4