H - Grid 1（動的計画法⑩）

問題

縦 H 行、横 W 列のグリッドがあります。 

上から i 行目、左から j 列目のマスを (i,j) で表します。

各 i, j ( 1 ≦ i ≦ H, 1 ≦ j ≦ W) について、マス (i, j) の情報が文字 a[i, j] によって与えられます。

a[i, j] が . ならばマス (i,j) は空マスであり、a[i, j] が # ならばマス (i, j) は壁のマスです。

マス (1, 1) および (H, W) は空のマスであることが保証されています。

マス (1, 1) から出発し、右または下に隣り合う空マスへの移動を繰り返すことで、マス (H,W) まで辿り着こうとしています。

マス (1, 1) から (H, W) までの経路は何通りあるでしょうか。

答えは非常に大きくなりうるので、10**9 + 7 で割った余りを求めてください。

解法・ソースコード

単純に 左上から右下までの経路 を求めるという問題で、移動するたびにカウントアップすれば経路の数を求めることができます。

もちろん移動先が壁の場合は、カウントアップしません。

また、問題文の最後にあるように、109 + 7を超えた場合は余りを求めるために 109 + 7を引いています。

（最後に 10**9 + 7 で割ってその余りを求める方法もありますが、カウントアップ途中で数字が大きくなりオーバーフローする可能性があります）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#--------- 入力例1 ----------
mp = ['...#',
      '.#..',
      '....']
#--------- 入力例2 ----------
# mp = ['..',
#       '#.',
#       '..',
#       '.#',
#       '..']
#--------- 入力例3 ----------
# mp = ['..#..',
#       '.....',
#       '#...#',
#       '.....',
#       '..#..']
#--------- 入力例4 ----------
# mp = ['....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................']
#----------------------------
H, W = len(mp), len(mp[0])
MOD = 10**9 + 7

# メモ化テーブル初期化
memo = [[0] * W for _ in range(H)]
# 初期条件
memo[0][0] = 1

# 全マス目を探索
for i in range(H):
    for j in range(W):
        if i + 1 < H and mp[i + 1][j] == '.':
            memo[i + 1][j] += memo[i][j]    # カウントアップ
            # 計算の途中で余りをとる
            if memo[i + 1][j] >= MOD:
                memo[i + 1][j] -= MOD
        if j + 1 < W and mp[i][j + 1] == '.':
            memo[i][j + 1] += memo[i][j]    # カウントアップ
            # 計算の途中で余りをとる
            if memo[i][j + 1] >= MOD:
                memo[i][j + 1] -= MOD

print('解：', memo[H - 1][W - 1])

[実行結果(入力例1)]

解： 3

経路は 3 通りあります。

[実行結果(入力例2)]

解： 0

経路が存在しません。

[実行結果(入力例3)]

解： 24

経路は 24 通りあります。

[実行結果(入力例4)]

解： 345263555

経路は 345263555 通りあります。

途中で 10**9 + 7 を超えているため、その余りが経路数となります。