通学路-PYTHON

問題の説明

持続的な豪雨が一部の地域を水没させた.水没していない地域を通って学校に行きたいです.家から学校までの道はm×nサイズのグリッドで表すことができます.
下図はm=4,n=3である.

最左上隅(すなわち家屋の所在地の座標)は(1,1)であり、最右下角(すなわち学校の所在地の座標)は(m,n)である.
グリッドサイズm、n、および水没領域座標を含む2 Dフラットピットにパラメータ化します.右側と下側だけに移動し、家から学校までの最短パスの数を1000000 7で割ってからソリューション関数に戻ってください.

せいげんじょうけん

メッシュのサイズm,nは1または100以下の自然数である.
mとnがともに1の場合、入力は提供されません.
水没した地域は0個または10個以上である.
家や学校が水没したら、入力は与えられません.

問題を解く

最初は問題を読み間違えて最小パス数を見つけたのでdfsで最小パスを探しました...もとは総経路の数です.🤦‍♂️
问题をよく読みなさい.
また、前回から問題を見ていると、練習帳で直接やって、そこでアルゴリズムを導出する方法を使っています.同様に、直接手でサンプルを描くことができるパスも探しています.
上のセルから来ることができるパス+左から来ることができるパスは、現在の位置に着くことができるパスです.
水たまりがあるので水たまりは行けないので0にリセットするアルゴリズムを見つけました.

地図を作成します.開始点は1で、残りは0にリセットされます.

地図を回って、上のパス+左のパスです.

ピットがある場合は0にリセットします.

def solution(m, n, puddles):
    maps = [[0]*(m+1) for _ in range(n+1)]
    maps[1][1] = 1
    for x in range (1,m+1):
        for y in range (1,n+1):
            if x == 1 and y == 1:
                continue
            if [x,y] in puddles:
                maps[y][x] = 0
            else:
                maps[y][x] += maps[y-1][x] + maps[y][x-1]
    
    answer = (maps[n][m]) % 1000000007
            
    return answer