Pythonで開始点から終了点までコストkのパスの数をカウントするプログラム

2次元のバイナリ行列と別の値kがあるとします。左上のセルから始めて、右下のセルに移動する必要があります。一歩で、私たちは下がるか、右に下がることしかできません。これで、パスのスコアは、パス上のセルの値の合計になります。スコアkで開始セルから終了セルまでのパスの数を見つける必要があります。考えられる方法が非常に多い場合は、結果mod 10 ^ 9+7を返します。

したがって、入力が次のような場合

K =2の場合、スコア2のパスは[R、R、D、D]、[D、R、R、D]、[D、D、R、R]、[D]であるため、出力は4になります。 、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]

• iがm-1と同じで、jがn-1と同じ場合、

  • ptsがkと同じ場合は1を返し、それ以外の場合は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