2차원 이진 행렬과 다른 값 k가 있다고 가정합니다. 이제 왼쪽 상단 셀에서 시작하여 오른쪽 하단 셀로 이동해야 합니다. 한 단계에서 우리는 아래로 또는 오른쪽으로만 갈 수 있습니다. 이제 경로의 점수는 경로의 셀에 있는 값의 합계입니다. 점수가 k인 시작 셀에서 끝 셀까지의 경로 수를 찾아야 합니다. 가능한 방법이 많다면 결과 모드 10^9+7을 반환하십시오.
따라서 입력이 다음과 같으면
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 0 |
K =2이면 점수가 2인 경로가 [R,R,D,D], [D,R,R,D], [D,D,R,R], [D이므로 출력은 4가 됩니다. ,R,D,R] 여기서 D는 아래로, R은 옳습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
데노 :=10^9 + 7
-
m :=행렬의 행 개수, n :=행렬의 열 개수
-
dfs() 함수를 정의합니다. 이것은 i, j, pts가 필요합니다.
-
i>=m 또는 j>=n이면
-
0 반환
-
-
pts :=pts + 행렬[i, j]
-
i가 m - 1과 같고 j가 n - 1과 같으면
-
pts가 k와 같으면 1을 반환하고 그렇지 않으면 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