สมมติว่าเรามีเมทริกซ์ไบนารี 2d และอีกค่าหนึ่งคือ k เริ่มจากเซลล์ด้านซ้ายบน เราต้องไปที่เซลล์ขวาล่าง ในขั้นตอนเดียวเราลงไปได้เท่านั้นหรือถูกต้อง ตอนนี้คะแนนของพาธคือผลรวมของค่าในเซลล์บนพาธ เราต้องหาจำนวนเส้นทางจากเซลล์เริ่มต้นไปยังเซลล์สิ้นสุดด้วยคะแนน k หากมีวิธีที่เป็นไปได้มากมาย ให้คืนค่า mod ผลลัพธ์ 10^9+7
ดังนั้นหากอินพุตเป็นแบบ
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 0 |
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
-
m :=จำนวนแถวของเมทริกซ์ n :=จำนวนคอลัมน์ของเมทริกซ์
-
กำหนดฟังก์ชัน dfs() นี่จะใช้เวลา i, j, pts
-
ถ้า i>=m หรือ j>=n แล้ว
-
คืนค่า 0
-
-
pts :=pts + matrix[i, j]
-
ถ้าฉันเหมือนกับ m - 1 และ j เหมือนกับ n - 1 แล้ว
-
คืนค่า 1 เมื่อ pts เหมือนกับ k มิฉะนั้น 0
-
-
ส่งคืน dfs(i + 1, j, pts) + dfs(i, j + 1, pts)
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
ส่งคืน dfs(0, 0, 0) mod 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
