Pythonで左上のポイントから右下のポイントに到達できる方法の数を見つけるためのプログラム

1つのNxMバイナリ行列があるとします。ここで、0は空のセルを意味し、1はブロックされたセルを意味します。左上隅から始めて、右下隅に到達する方法の数を見つける必要があります。答えが非常に大きい場合は、10 ^ 9+7で変更します。

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

右下に移動するには、[右、下、右、下]と[下、右、右、下]の2つの方法があるため、出力は2になります。

これを解決するには、次の手順に従います-

• dp：=指定された行列と同じサイズの行列で、0で埋めます
• dp [0、0]：=1
• 1から行列の行数までの範囲のiについては、
  • matrix [i、0]が1と同じ場合、
    • ループから抜け出す
  • それ以外の場合、
    • dp [i、0]：=1
• 1から行列の列数までの範囲のjについては、
  • matrix [0、j]が1と同じ場合、
    • ループから抜け出す
  • それ以外の場合、
    • dp [0、j]：=1
• 1から行列の行数までの範囲のiについては、
  • 1から行列の列数までの範囲のjについては、
    • matrix [i、j]が1と同じ場合、
      • dp [i、j]：=0
    • それ以外の場合、
      • dp [i、j]：=dp [i-1、j] + dp [i、j-1]
• dpの右下の値を返す

例（Python）

理解を深めるために、次の実装を見てみましょう-

class Solution:
   def solve(self, matrix):
      dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
      dp[0][0] = 1
      for i in range(1, len(matrix)):
         if matrix[i][0] == 1:
            break
         else:
            dp[i][0] = 1
      for j in range(1, len(matrix[0])):
         if matrix[0][j] == 1:
            break
         else:
            dp[0][j] = 1
      for i in range(1, len(matrix)):
         for j in range(1, len(matrix[0])):
            if matrix[i][j] == 1:
               dp[i][j] = 0
            else:
               dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
      return dp[-1][-1]
ob = Solution()
matrix = [
   [0, 0, 1],
   [0, 0, 0],
   [1, 1, 0]
]
print(ob.solve(matrix))

入力

matrix = [
[0, 0, 1],
[0, 0, 0],
[1, 1, 0] ]

出力

2