Problem:


Score : 100 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns.
Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.

For each i and j (1 \leq i \leq H, 1 \leq j \leq W), Square (i, j) is described by a character a_{i, j}.
If a_{i, j} is ., Square (i, j) is an empty square; if a_{i, j} is #, Square (i, j) is a wall square.
It is guaranteed that Squares (1, 1) and (H, W) are empty squares.

Taro will start from Square (1, 1) and reach (H, W) by repeatedly moving right or down to an adjacent empty square.

Find the number of Taro's paths from Square (1, 1) to (H, W).
As the answer can be extremely large, find the count modulo 10^9 + 7.

Constraints

H and W are integers.

2 \leq H, W \leq 1000

a_{i, j} is . or #.

Squares (1, 1) and (H, W) are empty squares.

Input

Input is given from Standard Input in the following format:

H W
a_{1, 1}\ldotsa_{1, W}
:
a_{H, 1}\ldotsa_{H, W}

Output

Print the number of Taro's paths from Square (1, 1) to (H, W), modulo 10^9 + 7.

Sample Input 1

3 4
...#
.#..
....

Sample Output 1

3

There are three paths as follows:

Sample Input 2

5 2
..
#.
..
.#
..

Sample Output 2

0

There may be no paths.

Sample Input 3

5 5
..#..
.....
#...#
.....
..#..

Sample Output 3

24

Sample Input 4

20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................

Sample Output 4

345263555

Be sure to print the count modulo 10^9 + 7.



Sample input:
3 4
...#
.#..
....


Sample output:
3

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    a = [i == '.' for i in input()]
    v = [0] * W
    v[0] = 1
    for j in range(1, W):
        if not a[j]:
            break
        v[j] = 1

    for i in range(1, H):
        a = [i == '.' for i in input()]
        u = v
        v = [0] * W
        v[0] = u[0] if a[0] else 0
        for j in range(1, W):
            v[j] = u[j] + v[j - 1] if a[j] else 0
    print(v[-1] % (10 ** 9 + 7))


main()

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    a = []
    for _ in range(H):
        a.append(input())
    b = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if a[i][j] == '#':
                b[i][j] = 0
                continue
            if i == 0 and j == 0:
                b[i][j] = 1
            elif i == 0:
                b[i][j] = b[i][j-1]
            elif j == 0:
                b[i][j] = b[i-1][j]
            else:
                b[i][j] = b[i-1][j] + b[i][j-1]
    print(b[-1][-1] % (10**9 + 7))

main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
buf = sys.stdin.buffer
mod = 10 ** 9 + 7

H, W = map(int, buf.readline().split())

grid = np.resize(np.frombuffer(buf.read(), dtype='S1') == b'.', (H, W + 1))[:, :-1] * 1

dp = np.zeros(W, np.int64)
dp[0] = 1

for i in grid:
    wall = (i == 0)
    dp[wall] = 0
    np.cumsum(dp, out=dp)
    dp -= np.maximum.accumulate(dp * wall)
    dp %= mod

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H,W = map(int,input().split())
mod = 10**9+7

A = [list(input()[:-1]) for _ in range(H)]

dp = [[0]*W for _ in range(H)]
dp[0][0]=1
for h in range(H):
    for w in range(W):
        if (h+1<H and A[h][w] == '.'):
            dp[h+1][w] += dp[h][w]
        if (w+1<W and A[h][w]=='.'):
            dp[h][w+1] += dp[h][w]
print(dp[H-1][W-1] % mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    A = [list(input()[:-1]) for _ in range(H)]

    dp = [[0]*W for _ in range(H)]
    dp[0][0] = 1
    for h in range(H):
        for w in range(W):
            if h+1<H and A[h][w]==".":
                dp[h+1][w] += dp[h][w]
            if w+1<W and A[h][w]==".":
                dp[h][w+1] += dp[h][w]
    
    print(dp[H-1][W-1]  % (10**9 + 7))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

H,W = map(int, input().split())
L = [input() for _ in range(H)]

dp = [[0]*W for _ in range(H)]
dp[0][0] = 1
used = [[0]*W for _ in range(H)]
q = deque()
q.append((0, 0))
while q:
    t = q.popleft()
    i = t[0]
    j = t[1]
    used[i][j] = 2
    if i != H-1 and L[i+1][j] == "." and used[i+1][j] < 2:
        dp[i+1][j] += dp[i][j]
        if used[i+1][j] == 0:
            q.append((i+1, j))
            used[i+1][j] = 1
    if j != W-1and L[i][j+1] == "." and used[i][j+1] < 2:
        dp[i][j+1] += dp[i][j]
        if used[i][j+1] == 0:
            q.append((i, j+1))
            used[i][j+1] = 1
        
print(dp[H-1][W-1]%(10**9+7))

Submission status: Accepted

Solution code:
H,W = [int(s) for s in input().split()]
dp = [[0]*(1001) for _ in range(1001)]
dp[0][0] = 1

a = [[0]*W for _ in range(H)]
for i in range(H):
    lis = list(input())
    for j in range(W):
        a[i][j] = lis[j]

for i in range(H):
    for j in range(W):
        if i+1 < H and a[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
        if j+1 < W and a[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
ans = dp[H-1][W-1]%(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
H,W = map(int,input().split())
A = [input() for _ in range(H)]
dp = [[0] * (W+1) for _ in range(H+1)]
dp[0][1] = 1
for w in range(W):
    for h in range(H):
        if A[h][w] == ".":
            dp[h+1][w+1] = dp[h][w+1] + dp[h+1][w]
            dp[h+1][w+1] %= mod
print(dp[H][W])

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
mod = 10**9 + 7
data = [input() for _ in range(h)]
dp = [[0 for _ in range(w)] for i in range(h)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if data[i][j] == '.':
            if i > 0:
                dp[i][j] += dp[i-1][j]
            if j > 0:
                dp[i][j] += dp[i][j-1]
            dp[i][j] %= mod

print(dp[h-1][w-1])

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
mod = 10**9 + 7
data = [input() for _ in range(h)]
dp = [[0 for _ in range(w)] for i in range(h)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if data[i][j] == '.':
            if i > 0 and data[i-1][j] == '.':
                dp[i][j] += dp[i-1][j]
            if j > 0 and data[i][j-1] == '.':
                dp[i][j] += dp[i][j-1]
            dp[i][j] %= mod

print(dp[h-1][w-1])

Submission status: Accepted

Solution code:
R, C = map(int, input().split())
arr = [list(input()) for _ in range(R)]
dp = [[0 for _ in range(C+1)] for _ in range(R+1)]
dp[1][1] = 1
for i in range(1, R+1):
    for j in range(1, C+1):
        if arr[i-1][j-1] == "#":
            dp[i][j] = 0
        else:
            dp[i][j] = max(dp[i][j], dp[i-1][j]+dp[i][j-1])%1000000007
 
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H, W = list(map(int, input().split()))
A = []
DP = []

for _ in range(H):
    a = list(input().strip())
    A.append(a)
    DP.append([0] * W)


MOD = 10 ** 9 + 7
DP[0][0] = 1

for x in range(W):
    for y in range(H):
        if y + 1 < H and A[y+1][x] == ".":
            DP[y+1][x] = (DP[y+1][x] + DP[y][x]) % MOD
        if x + 1 < W and A[y][x+1] == ".":
            DP[y][x+1] = (DP[y][x+1] + DP[y][x]) % MOD

print(DP[H-1][W-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(H: int, W: int, a: "[List[str]"):
    dp = [[0] * (W+1) for i in range(H+1)]

    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            
            if 0 <= i < H and 0 <= j+1 < W and a[i][j+1] == '.':
                dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % MOD
            if 0 <= i+1 < H and 0 <= j < W and a[i+1][j] == '.':
                dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD


    print(dp[H-1][W-1])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    a = [ next(tokens) for _ in range(H) ]  # type: "List[List[str]]"
    solve(H, W, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = [input() for _ in range(H)]
MOD = 10**9+7

dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1

for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      dp[i][j] = 0
    else:
      if j > 0:
        dp[i][j] += dp[i][j-1]
      if i > 0:
        dp[i][j] += dp[i-1][j]
    dp[i][j] %= MOD

print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
a = [list(map(str, list(input()))) for i in range(H)]

DP = [[0] * W for i in range(H)]

DP[0][0] = 1

Big = 1000000007

for i in range(H):
    for j in range(W):

        if DP[i][j] == 0 and a[i][j] == ".":
            up = 0
            le = 0

            if i > 0 and a[i - 1][j] == ".":
                up = DP[i - 1][j]
                
            if j > 0 and a[i][j - 1] == ".":
                le = DP[i][j - 1]

            DP[i][j] = ((up % Big) + (le % Big)) % Big           
            
print(DP[H-1][W-1])

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
F = []
for i in range(N):
    F.append(input())
W = [[0] * M for _ in range(N)]
for i in range(N):
    if F[i][0] == "#":
        break
    W[i][0] = 1
for i in range(M):
    if F[0][i] == "#":
        break
    W[0][i] = 1       
for i in range(1, N):
    for j in range(1, M):
        if F[i][j] != "#":
            W[i][j] += W[i-1][j]
            W[i][j] += W[i][j-1]
print(W[-1][-1] % (10**9+7))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(input().strip())

    dp = [[0]*W for _ in range(H)]
    x = 1
    for w in range(W):
        if A[0][w] == "#":
            x = 0
        dp[0][w] = x
    x = 1
    for h in range(H):
        if A[h][0] == "#":
            x = 0
        dp[h][0] = x

    for h in range(1, H):
        for w in range(1, W):
            if A[h][w] == ".":
                dp[h][w] = dp[h-1][w] + dp[h][w-1]
            else:
                dp[h][w] = 0

    print(dp[-1][-1] % (10**9+7))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
a = [input() for _ in range(H)]
dp = [[0] * (W+1) for _ in range(H+1)]
ans = int(0)
mod = int(1000000007)
dp[1][1] = int(1)

for i in range(H):
    for j in range(W):
        if not(i==0 and j==0):
            if a[i][j] == ".":
#                print("Y",i,j)
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
            else:
                dp[i + 1][j + 1] = 0

print(dp[H][W]%mod)

Submission status: Accepted

Solution code:

def count(a,h,w):
    for i in range(h):
        if a[i][0]==0:
            a[i][0]=1
        else:
            break
    for i in range(1,w):
        if a[0][i]==0:
            a[0][i]=1
        else:
            break
    for i in range(1,h):
        for j in range(1,w):
            if a[i][j]==-1:
                continue
            if a[i-1][j]>0:
                a[i][j]=a[i][j]+a[i-1][j]
            if a[i][j-1]>0:
                a[i][j]=a[i][j]+a[i][j-1]
    if a[h-1][w-1]>0:
        return a[h-1][w-1]
    else:
        return 0

h,w = list(map(int,input().split()))
a = [list(input()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]==".":
            a[i][j] = 0
        else:
            a[i][j] = -1
print(count(a,h,w)%(10**9+7))

Submission status: Accepted

Solution code:
# 配るDP
H, W = map(int, input().split())
a = [input() for _ in range(H)]

dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
for h in range(H - 1):
  for w in range(W - 1):
    if a[h][w] == '#':
      continue
    if a[h][w + 1] != '#':
      dp[h][w + 1] = (dp[h][w + 1] + dp[h][w]) % 1000000007
    if a[h + 1][w] != '#':
      dp[h + 1][w] = (dp[h + 1][w] + dp[h][w]) % 1000000007
  if a[h][W - 1] == '#':
    continue
  if a[h + 1][W - 1] != '#':
    dp[h + 1][W - 1] = (dp[h + 1][W - 1] + dp[h][W - 1]) % 1000000007
for w in range(W - 1):
  if a[H - 1][w] == '#':
    continue
  if a[H - 1][w + 1] != '#':
    dp[H - 1][w + 1] = (dp[H - 1][w + 1] + dp[H - 1][w]) % 1000000007

print(dp[H - 1][W - 1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
a = [input() for _ in range(H)]

dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
for w in range(1, W):
  if a[0][w] != '#':
    dp[0][w] = dp[0][w - 1]

for h in range(1, H):
  if a[h][0] != '#':
    dp[h][0] = dp[h - 1][0]
  for w in range(1, W):
    if a[h][w] != '#':
      dp[h][w] = (dp[h][w - 1] + dp[h - 1][w]) % 1000000007

print(dp[H - 1][W - 1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
a = [input() for _ in range(H)]

dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
for w in range(1, W):
  if a[0][w] != '#':
    dp[0][w] = dp[0][w - 1]

for h in range(1, H):
  ah = a[h]
  dph = dp[h]
  dph1 = dp[h - 1]
  if ah[0] != '#':
    dph[0] = dph1[0]
  for w in range(1, W):
    if ah[w] != '#':
      dph[w] = (dph[w - 1] + dph1[w]) % 1000000007

print(dp[H - 1][W - 1])

Submission status: Accepted

Solution code:
h,w = (int(i) for i in input().split())

arr = [[(-1 if i=='#' else 0) for i in input()] for j in range(h)]

metWall = False
for j in range(w):
    if metWall:
        arr[0][j] = 0
    else:
        if (arr[0][j]==-1):
            arr[0][j] = 0
            metWall = True
        else:
            arr[0][j] = 1

for i in range(1,h):
    for j in range(w):
        this = arr[i][j]
        if this==-1:
            arr[i][j] = 0
        else:
            arr[i][j] = (arr[i][j-1] if j>0 else 0)+arr[i-1][j]

print(arr[-1][-1]%1000000007)

Submission status: Accepted

Solution code:
h , w = [int(x) for x in input().strip().split()]
mat = []
for _ in range(h):
    mat.append(input())

dp = [[0 for i in range(w)] for j in range(h)]
dp[0][0] = 1
mod = 10**9+7
for i in range(h):
    for j in range(w):
        if mat[i][j]=='#':
            dp[i][j] = 0
        elif i==0 and j==0:
            pass
        elif j<1 and i>=1:
            dp[i][j] = dp[i-1][j]%mod
        elif i<1 and j>=1:
            dp[i][j] = dp[i][j-1]%mod
        else:
            dp[i][j] = ((dp[i][j-1]%mod)+(dp[i-1][j]%mod))%mod

print(dp[h-1][w-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
mod = 10**9 + 7
field = []
for i in range(H):
    S = input()
    field.append(S)

dp = [[0]*W for i in range(H)]

#端っこ
dp[0][0] = 1
# 縦
for i in range(1,H):
    if field[i][0] == ".":
        dp[i][0] = dp[i-1][0]
    else:dp[i][0] = 0
# 横
for j in range(1,W):
    if field[0][j] == ".":
        dp[0][j] = dp[0][j-1]
    else:
        dp[0][j] = 0

for i in range(1,H):
    for j in range(1,W):
        if field[i][j] == ".":
            dp[i][j] = dp[i][j-1]+dp[i-1][j]
            
print(dp[H-1][W-1]%mod)
# print(dp)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H,W=map(int,input().split())
a = [list(input().split()) for _ in range(H)]
for i in range(H):
    a[i] = list(a[i][0])
MOD=1000000007
dp = [[0]*W for _ in range(H)]
dp[0][0]=1
for h in range(H):
    for w in range(W):
        if a[h][w]=="#": continue
        if h-1>=0: dp[h][w]+=dp[h-1][w]
        if w-1>=0: dp[h][w]+=dp[h][w-1]
        dp[h][w]%=MOD
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
#Grid1
mod=10**9+7
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
dp=[[0]*(w) for i in range(h)]
for i in range(w):
    if a[0][i]==".":
        dp[0][i]=1
    else:
        break
for i in range(h):
    if a[i][0]==".":
        dp[i][0]=1
    else:
        break
for i in range(1,h):
    for j in range(1,w):
        if a[i][j]=="#":
            dp[i][j]=0
        else:
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
print(dp[h-1][w-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#EDPC H

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
maze = [input() for _ in range(h)]
dp = [[0]*w for _ in range(h)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            if j == 0:
                if i+1 < h:
                    if maze[i+1][j] == '.':
                        dp[i+1][j] += dp[i][j]
                        dp[i+1][j] %= mod
            else:
                dp[i][j] += dp[i][j-1]
                dp[i][j] %= mod
                if i+1 < h:
                    if maze[i+1][j] == '.':
                        dp[i+1][j] += dp[i][j]
                        dp[i+1][j] %= mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
M = [input() for i in range(H)]
dp = [[0 for i in range(W)] for j in range(H)]
dp[0][0] = 1

for i in range(H):
  for j in range(W):
    if i+1 < H and M[i+1][j] == ".":
      dp[i+1][j] = dp[i][j]
    if j+1 < W and M[i][j+1] == ".":
      dp[i][j+1] += dp[i][j]

print(dp[H-1][W-1] % (10**9+7))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
M = [input() for i in range(H)]
dp = [[0 for i in range(W+1)] for j in range(H+1)]
dp[1][1] = 1

for i in range(1, H+1):
  for j in range(1, W+1):
    if i == 1 and j == 1:
      continue
    if M[i-1][j-1] == "#":
      continue
    dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[H][W] % (10**9+7))

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function
from collections import defaultdict, Counter, deque
from future_builtins import ascii, filter, hex, map, oct, zip
from itertools import imap as map, izip as zip
from itertools import permutations
from __builtin__ import xrange as range
from math import ceil
from _continuation import continulet
from cStringIO import StringIO
from io import IOBase
import __pypy__
from math import log, ceil, floor
from bisect import bisect, insort, bisect_left, bisect_right
from heapq import heapify, heappop, heappush
import sys
import os
import re
inf = float('inf')
mod = int(1e9) + 7
mod_ = 998244353
 
'''

!!!!!!!!!!!!!!!!!!!!!!!!   WAIT FFS    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
DONOT SUBMIT RECKLESSLY
One wrong submission = 10 mins penalty!
Check for special cases (n=1)

'''


def printGrid(grid):
	for row in grid:
		print(' '.join(list(map(str, row))))

def main():
	n, m = map(int, input().split())
	grid = [list(input()) for i in range(n)]
	dp = [[0]*m for i in range(n)]
	for i in range(m):
		if grid[0][i] == '#':
			for j in range(i, m):
				dp[0][j] = 0
			break
		dp[0][i] = 1

	for i in range(n):
		if grid[i][0] == '#':
			for j in range(i, n):
				dp[j][0] = 0
			break
		dp[i][0] = 1

	for i in range(1, n):
		for j in range(1, m):
			if grid[i][j] == '.':
				dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod

	print(dp[-1][-1])

# Fast IO
BUFSIZE = 8192
class FastI(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = StringIO()
		self.newlines = 0
 
	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0
		return self.buffer.read()
 
	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count("\n") + (not b)
			ptr = self._buffer.tell()
			self._buffer.seek(0, 2), self._buffer.write(
				b), self._buffer.seek(ptr)
		self.newlines -= 1
		return self._buffer.readline()
class FastO(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = __pypy__.builders.StringBuilder()
		self.write = lambda s: self._buffer.append(s)
 
	def flush(self):
		os.write(self._fd, self._buffer.build())
		self._buffer = __pypy__.builders.StringBuilder()
def print(*args, **kwargs):
	sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop("end", "\n"))
	if kwargs.pop("flush", False):
		file.flush()
def gcd(x, y):
	while y:
		x, y = y, x % y
	return x
sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")
if __name__ == "__main__":
	def bootstrap(cont):
		call, arg = cont.switch()
		while True:
			call, arg = cont.switch(to=continulet(
				lambda _, f, args: f(*args), call, arg))
	cont = continulet(bootstrap)
	cont.switch()
	main()

Submission status: Accepted

Solution code:
def h_grid1(MOD=10**9 + 7):
    H, W = [int(i) for i in input().split()]
    Grid = ['#' * (W + 1)] + ['#' + input() for _ in range(H)]  # 左と上を埋める

    # path[r][c]: マス(r, c)に(0-based)到達する経路の数
    path = [[0] * (W + 1) for _ in range(H + 1)]
    path[0][1] = 1  # path[1][1] = 1 (スタート地点) とするための便宜上の代入

    for row in range(1, H + 1):
        for col in range(1, W + 1):
            if Grid[row][col] == '.':
                path[row][col] = (path[row - 1][col] + path[row][col - 1]) % MOD
    return path[H][W]

print(h_grid1())

Submission status: Accepted

Solution code:
def h_grid1(MOD=10**9 + 7):
    H, W = [int(i) for i in input().split()]
    Grid = [input() for _ in range(H)]

    # path[r][c]: マス(r, c)に(0-based)到達する経路の数
    path = [[0] * W for _ in range(H)]
    path[0][0] = 1  # スタート地点は必ず到達できる

    def can_reach(row, col):
        return 0 <= row < H and 0 <= col < W and Grid[row][col] == '.'

    for row in range(H):
        for col in range(W):
            if Grid[row][col] == '#':
                continue
            for nr, nc in ((row, col + 1), (row + 1, col)):
                if can_reach(nr, nc):
                    path[nr][nc] += path[row][col]
                    path[nr][nc] %= MOD
    return path[H - 1][W - 1]

print(h_grid1())

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
a = [input() for _ in range(H)]
dp = [[0 for _ in range(W+1)] for __ in range(H+1)]
dp[1][0]=1
mod_numb = 1000000007
for h in range(1,H+1):
    for w in range(1,W+1):
        if a[h-1][w-1]=='#':
            continue
        else:
            dp[h][w] = (dp[h-1][w] + dp[h][w-1])%mod_numb
print(dp[H][W])

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

h, w = map(int, input().split())
a = tuple(input() for _ in range(h))

dp = [[0] * w for _ in range(h)]
dp[0][0] = 1

# 配る
for r in range(h):
    for c in range(w):
        if a[r][c] == '#':
            continue
        if r + 1 < h and a[r + 1][c] == '.':
            dp[r + 1][c] = (dp[r + 1][c] + dp[r][c]) % mod
        if c + 1 < w and a[r][c + 1] == '.':
            dp[r][c + 1] = (dp[r][c + 1] + dp[r][c]) % mod
print(dp[h - 1][w - 1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())

mod = pow(10, 9) + 7

grid = [
    [1 if c == '#' else 0 for c in input()]
    for row in range(H)]

dp = [[0 for i in range(W)] for j in range(H)]

dp[0][0] = 1

for y in range(H):
    for x in range(W):
        # Move down
        if y > 0 and not grid[y-1][x]:
            dp[y][x] += dp[y-1][x]

        # Move right
        if x > 0 and not grid[y][x-1]:
            dp[y][x] += dp[y][x-1]
            
        dp[y][x] %= mod

print(dp[-1][-1])

Submission status: Accepted

Solution code:
mod=1000000007
h,w=map(int,input().split())
p=[]
ans=[[0]*w for i in range(h)]
for i in range(h):
    p.append(input())
ans[0][0]=1
for i in range(h):
    for j in range(w):
        if p[i][j]=="#":
            ans[i][j]=0
        elif i==0 and j!=0:
            ans[0][j]=ans[0][j-1]
        elif i!=0 and j==0:
            ans[i][0]=ans[i-1][0]
        elif i!=0 and j!=0:
            ans[i][j]=(ans[i-1][j]+ans[i][j-1])%mod
print(ans[h-1][w-1])

Submission status: Accepted

Solution code:
h, w = map(int, input().split( ))
a = []
m = 10**9+7
for i in range(h):
    inpt = input()
    a.append(inpt)

DP = [[0 for j in range(w)] for i in range(h)]

DP[0][0] = 1###

for i in range(h):
    for j in range(w):
        if i!=0 or j !=0:###
            if a[i][j] == "#":
                pass
            else:
                DP[i][j] = DP[i-1][j]+DP[i][j-1]
        DP[i][j] %=m
print(DP[h-1][w-1])

Submission status: Accepted

Solution code:
H, W = list(map(int, input().split()))
A = [['' for i in range(W + 1)] for j in range(H + 1)]
dp = [[0 for i in range(W + 1)] for j in range(H + 1)]
for i in range(1, H + 1):
    a = input()
    for j in range(W):
        A[i][j + 1] = a[j]
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if A[i][j] == '#':
            dp[i][j] = 0
        elif i == 1 and j == 1:
            dp[i][j] = 1
        elif i == 1:
            dp[i][j] = dp[i][j - 1]
        elif j == 1:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
print(dp[H][W] % 1000000007)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
h, w = [int(i) for i in sys.stdin.readline().split()]
MAP = []
memo_ls = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    inp = [0 if i == "." else 1 for i in input()]
    MAP.append(inp)


memo_ls[h-1][w-1] = 1
for _h in range(h-1,-1,-1):
    for _w in range(w-1,-1,-1):
        if MAP[_h][_w] == 1:
            continue
        if _w < w - 1:
            memo_ls[_h][_w] += memo_ls[_h][_w+1]
        if _h < h - 1:
            memo_ls[_h][_w] += memo_ls[_h+1][_w]
        memo_ls[_h][_w] %= (1e9+7)
print(int(memo_ls[0][0] % (1e9+7)))

Submission status: Accepted

Solution code:
# At DP F
def paths(M):
    A = [ [0] * len(M[0]) for _ in range(len(M)) ]
    A[0][0] = 1
    for row in range(len(A)):
        for col in range(len(A[row])):
            count = A[row][col]
            if row > 0 and M[row - 1][col] != '#':
                count += A[row - 1][col]
            if col > 0 and M[row][col - 1] != '#':
                count += A[row][col - 1]
            A[row][col] = count
    return A[-1][-1] % 1000000007

X1 = [
    "...#",
    ".#..",
    "...."
]

assert paths(X1) == 3

X2 = [
  "..",
  "#.",
  "..",
  ".#",
  "..",
]

assert paths(X2) == 0

X3 = [
    "..#..",
    ".....",
    "#...#",
    ".....",
    "..#.."
]

assert paths(X3) == 24

X4 = [
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
]
assert paths(X4) == 345263555

h, w = map(int, input().split())
M = [ None ] * h

for i in range(h):
    row = input().strip()
    M[i] = row

ans = paths(M)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    H, W = LI()
    maze = [SI() for _ in range(H)]

    ans = [[0 for _ in range(W+1)] for _ in range(H+1)]  # 1つ加えることで番兵とする。Python の場合、[-1] == [N-1] なので、上下左右に加えなくても、右と下に加えるだけでいい（ナナメ移動があるときは注意）。
    ans[0][0] = 1

    for j in range(W):
        for i in range(H):
            if (i, j) == (0, 0): continue
            if maze[i][j] == '#':
                continue
            else:
                ans[i][j] = (ans[i-1][j] + ans[i][j-1])%MOD

    print(ans[H-1][W-1])

main()

Submission status: Accepted

Solution code:
R, C = map(int, input().split())
grids = [list(input()) for _ in range(R)]
dp = [[0] * (C) for _ in range(R)]
dp[0][0] = 1
for i in range(1, R):
  if grids[i][0] != '#':
    dp[i][0] = dp[i-1][0]
for i in range(1, C):
  if grids[0][i] != '#':
    dp[0][i] = dp[0][i-1]
for i in range(1, R):
  for j in range(1, C):
    if grids[i][j] == '#':
      dp[i][j] = 0
    else:
      dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[R-1][C-1]%(10**9+7))

Submission status: Accepted

Solution code:
def main():

    H, W = map(int, input().split())
    mod = pow(10, 9) + 7
    A = []
    for _ in range(H):
        A.append(input())

    dp = [[0 for _ in range(W+1)] for _ in range(H+1)]

    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                dp[i+1][j+1] = 1
            elif A[i][j] == "#":
                dp[i+1][j+1] == -1
            else:
                v = 0
                if dp[i][j+1] != -1:
                    v += dp[i][j+1]
                if dp[i+1][j] != -1:
                    v += dp[i+1][j]
                dp[i+1][j+1] = v % mod

    return dp[H][W]
if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
y_map, x_map = map(int, input().split())
field_map = [list(input()) for i in range(y_map)]

dp = [[0 for i in range(x_map+1)]for j in range(y_map+1)]
dp[1][1] = 1
for i in range(y_map):
    for j in range(x_map):
        if field_map[i][j] == ".":
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j] + dp[i][j+1])
        else:
            dp[i+1][j+1] = 0

print(dp[-1][-1]%((10**9)+7))