Giả sử chúng ta có một ma trận nhị phân 2d và một giá trị khác k. Bây giờ bắt đầu từ ô trên cùng bên trái, chúng ta phải chuyển đến ô dưới cùng bên phải. Trong một bước, chúng ta chỉ có thể đi xuống hoặc sang phải. Bây giờ điểm của một đường dẫn là tổng các giá trị trên các ô trên đường dẫn. Chúng ta phải tìm số đường đi từ ô bắt đầu đến ô kết thúc với điểm k. Nếu có rất nhiều cách có thể, hãy trả về kết quả mod 10 ^ 9 + 7.
Vì vậy, nếu đầu vào giống như
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 0 |
K =2, thì đầu ra sẽ là 4, vì các đường dẫn có điểm 2 là [R, R, D, D], [D, R, R, D], [D, D, R, R], [D , R, D, R] ở đây D là giảm và R đúng.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
biểu thị:=10 ^ 9 + 7
-
m:=số hàng của ma trận, n:=số cột của ma trận
-
Định nghĩa một hàm dfs (). Điều này sẽ mất i, j, pts
-
nếu tôi> =m hoặc j> =n, thì
-
trả về 0
-
-
pts:=pts + matrix [i, j]
-
nếu tôi giống với m - 1 và j giống với n - 1, thì
-
trả về 1 khi pts giống k, ngược lại là 0
-
-
trả về dfs (i + 1, j, pts) + dfs (i, j + 1, pts)
-
Từ phương thức chính, hãy làm như sau -
-
return dfs (0, 0, 0) mod mẫu
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[ [0, 0, 1], [1, 0, 1], [0, 1, 0] ], 2
Đầu ra
4