Submission #18162727

---

Source Code Expand

import sys


def IN_I(): return int(sys.stdin.readline().rstrip())
def IN_LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def IN_S(): return sys.stdin.readline().rstrip()
def IN_LS(): return list(sys.stdin.readline().rstrip().split())
INF = float('inf')
MOD = 10**9 + 7


H, W = IN_LI()
S = [IN_S() for _ in range(H)]
dp = [[0] * W for _ in range(H)]
dpx = [[0] * W for _ in range(H)]
dpy = [[0] * W for _ in range(H)]
dpxy = [[0] * W for _ in range(H)]
dp[0][0] = 1

for i in range(H):
    for j in range(W):
        if i == j == 0:
            continue
        if S[i][j] == '#':
            continue
        if j > 0:
            dpx[i][j] = (dpx[i][j-1] + dp[i][j-1])%MOD
        if i > 0:
            dpy[i][j] = (dpy[i-1][j] + dp[i-1][j])%MOD
        if i > 0 and j > 0:
            dpxy[i][j] = (dpxy[i-1][j-1] + dp[i-1][j-1])%MOD
        dp[i][j] = (dpx[i][j] + dpy[i][j] + dpxy[i][j])%MOD
print(dp[-1][-1])

Submission Info

Judge Result