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

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

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

K =2, तो आउटपुट 4 होगा, क्योंकि स्कोर 2 वाले पथ हैं [R,R,D,D], [D,R,R,D], [D,D,R,R], [D ,R,D,R] यहाँ D नीचे है और R सही है।

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

• deno :=10^9 + 7

• एम:=मैट्रिक्स की पंक्ति गणना, एन:=मैट्रिक्स की कॉलम गणना

• फ़ंक्शन को परिभाषित करें dfs() । इसमें i, j, pts लगेंगे

• अगर मैं>=मी या जे>=n, तो

  • वापसी 0

• अंक :=अंक + मैट्रिक्स[i, j]

• अगर मैं एम -1 के समान हूं और जे एन -1 के समान है, तो

  • 1 लौटाएं जब अंक k के समान हों अन्यथा 0

• वापसी dfs (i + 1, j, pts) + dfs (i, j + 1, pts)

• मुख्य विधि से निम्न कार्य करें -

• वापसी dfs(0, 0, 0) मॉड डेनो

उदाहरण

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

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