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:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass


n,m=L()
A=[input() for i in range(n)]
dp=[[0 for i in range(m)] for j in range(n)]
for i in range(n):
    for j in range(m):
        if i==0 and j==0:
            dp[i][j]=1
            continue
        if i==0:
            if A[i][j]==".":
                dp[i][j]=dp[i][j-1]
        elif j==0:
            if A[i][j]==".":
                dp[i][j]=dp[i-1][j]
        else:
            if A[i][j]==".":
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
            else:
                dp[i][j]=0
    # print(*dp[i])
print(dp[-1][-1])



endtime = time.time()
# print(f"Runtime of the program is {endtime - starttime}")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def ints(): return list(map(int, readline().split()))


def read_map_as(H, replace={'#': 1, '.': 0}, pad=None):
    '''
    文字列のmapを置換して読み込み。デフォでは#→1,.→0
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            # 内包表記はpypyでは若干遅いことに注意
            # #numpy使うだろうからこれを残しておくけど
    else:  # paddingする
        ret = [[pad] * (W + 2)]  # Wはどっかで定義しておくことに注意
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


MOD = 10**9 + 7

import numpy as np
H, W = ints()
A = np.array(read_map_as(H))


from numba import njit


@njit('(i8,i8,i8[:,:])', cache=True)
def solve(H, W, A):
    dp = np.zeros((H, W), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(H):
        for j in range(W):
            if A[i, j] == 0:
                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])


solve(H, W, A)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def ints(): return list(map(int, readline().split()))


def read_map_as(H, replace={'#': 1, '.': 0}, pad=None):
    '''
    文字列のmapを置換して読み込み。デフォでは#→1,.→0
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            # 内包表記はpypyでは若干遅いことに注意
            # #numpy使うだろうからこれを残しておくけど
    else:  # paddingする
        ret = [[pad] * (W + 2)]  # Wはどっかで定義しておくことに注意
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


MOD = 10**9 + 7

import numpy as np
H, W = ints()
A = np.array(read_map_as(H))


from numba import njit


@njit('(i8,i8,i8[:,:])', cache=True)
def solve(H, W, A):
    dp = np.zeros((H, W), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(H):
        for j in range(W):
            if A[i, j] == 1:
                dp[i, j] = 0
                continue
            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])


solve(H, W, A)

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

H,W=list(map(int,input().split()))
a = [ input().rstrip() for _ in range(H)]
dp = [[0]*(W) for _ in range(H)]
dp[0][0]=1
m=10**9+7
for ih in range(H):
    for iw in range(W):
        if a[ih][iw] == '#':
            dp[ih][iw] = 0
        else:
            if ih>0 and dp[ih-1][iw] >0:
                dp[ih][iw] += dp[ih-1][iw]
                dp[ih][iw] %=m
            if iw>0 and dp[ih][iw-1] >0:
                dp[ih][iw] += dp[ih][iw-1]
                dp[ih][iw] %=m
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def recursive(i,j):
    if i<0 or j<0 or i>=row or j>=col or  grid[i][j]=='#':
        return 0
    if dp[i][j]!=-1:
        return dp[i][j]
    if i==row-1 and j==col-1:
        return 1
    mod=10**9+7
    dp[i][j]=recursive(i+1,j)%mod +recursive(i,j+1)%mod
    return dp[i][j]%mod


row,col=map(int,input().split())
dp=[[-1]*col for _ in range(row)]
grid=[]
for _ in range(row):
    grid.append(input())
print(recursive(0,0))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n, m= list(map(int,input().split()))
arr = []
for i in range(n):
    arr.append(list(input()))
dp = []
dp.append([0]*(m+1))
for i in range(n):
    dp.append([0]+[1]*(m))
dp[1][1] = 1
for i in range(n):
    for g in range(m):
        dp[1][1] = 1
        if arr[i][g] != "#":
            dp[i+1][g+1] = (dp[i][g+1]+dp[i+1][g])%1000000007
        else:
            dp[i+1][g+1] = 0
print(dp[n][m])

Submission status: Accepted

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():
    mod = 10**9+7
    h, w = mi()
    g = [[] for _ in range(h+1)]
    g[0] = '#'*(w+1)
    for i in range(h):
        g[i+1] = '#'+input()
    dp = np.zeros((h+1, w+1), dtype=int)
    dp[1][1] = 1
    for i in range(1, h+1):
        for j in range(1, w+1):
            if g[i][j] == '#':
                dp[i][j] = 0
                continue
            dp[i][j] = max(dp[i][j], dp[i-1][j]+dp[i][j-1])
            dp[i][j] %= mod
    print(dp[h][w])
            
            

    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())

maze=[[i for i in input()] for _ in range(h)]

que=deque([[0,0]])

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

while que:
    n=que.popleft()
    x,y=n[0],n[1]

    if n==(h-1,w-1):
        break

    for i, j in [(1,0), (0,1)]:
        if (x+i >=w) or (y+j >=h) or maze[y+j][x+i] == '#':
            continue
        if visited[y+j][x+i] == 0:
            que.append([x+i,y+j])
        visited[y+j][x+i] += visited[y][x]

print(visited[h-1][w-1]%(10**9+7))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
grid = [list('#' * (W+1))]
for _ in range(1, H+1):
    temp = list(input())
    temp = ['#'] + temp
    grid.append(temp)
dp = [[0] * (W+1) for _ in range(H+1)]
dp[0][1] = 1
mod = 10**9 + 7

for i in range(1, H+1):
    for j in range(1, W+1):

        if grid[i][j] == '.':
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
            dp[i][j] %= mod
            
print(dp[H][W])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100007)

def main():
    h, w = map(int, input().split())
    grid = [None]*h
    for i in range(h):
        grid[i] = input()
    
    mod = pow(10, 9)+7
    dp = [[0]*w for _ in range(h)]
    dp[0][0] = 1
    for i in range(h):
        for j in range(w):
            dp[i][j] %= mod
            if i != h-1 and grid[i+1][j] == ".":
                dp[i+1][j] += dp[i][j]
            if j != w-1 and grid[i][j+1] == ".":
                dp[i][j+1] += dp[i][j]
    
    print(dp[h-1][w-1])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

grid = [input() for _ in range(H)]
# print(grid)

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

dp[1][1] = 1
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if not (i == 1 and j == 1):
            if grid[i - 1][j - 1] == "#":
                dp[i][j] = 0
            else:
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % (10**9 + 7)

# print(dp)
ans = dp[-1][-1]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 1000000007

H,W = map(int,input().split())
root = []
for _ in range(H):
    s = list(input())
    root.append(s)

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

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

Submission status: Accepted

Solution code:
mod = 1000000007

H,W = map(int,input().split())
root = []
for _ in range(H):
    s = list(input())
    root.append(s)

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

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
H, W = map(int, input().split())
a = [list(input()) for i in range(H)]
dp = [[0]*(W+1) for i in range(H+1)]
dp[0][1] = 1
mod = 10**9 + 7
for i in range(1, H+1):
    for j in range(1, W+1):
        if a[i-1][j-1] == ".":
            dp[i][j] += dp[i-1][j] + dp[i][j-1]
            dp[i][j] %= mod
            
ans =dp[H][W]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

H, W = map(int, input().split())
field = [input() for i in range(H)]
route_count_memory = [[-1] * W for i in range(H)]
route_count_memory[0][0] = 1

def get_route_count(i,j):
    result = 0
    if route_count_memory[i][j] != -1:
        return route_count_memory[i][j]
    if 0 <= i-1 < H and field[i-1][j] != '#':
        result += get_route_count(i-1, j)
    if 0 <= j-1 < W and field[i][j-1] != '#':
        result += get_route_count(i, j-1)
    route_count_memory[i][j] = result
    return result

print(get_route_count(H-1, W-1)%(10**9+7))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
grid = [str(input()) for _ in range(h)]
dp = [[0] * 1050 for _ in range(1050)]
MOD = int(1e9+7)
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        dp[i][j] %= MOD
        if i + 1 < h and grid[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
        if j + 1 < w and grid[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
print(dp[h-1][w-1])

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
grid = [str(input()) for _ in range(h)]
dp = [[0] * 1050 for _ in range(1050)]
MOD = int(1e9+7)
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if i + 1 < h and grid[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
        if j + 1 < w and grid[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
        dp[i][j] %= MOD
print(dp[h-1][w-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
a = [list(input().split(" ")) for _ in range(H)]
dp = [[-1] * (W + 1) for _ in range(H + 1)]

#print(a)

def f(y, x):
    if dp[y][x] != -1:
        return dp[y][x]
    res = 0
    if x == W:
        res = f(y + 1, x)
    elif y == H:
        res = f(y, x + 1)
    else:
        res = f(y, x + 1) + f(y + 1, x)
    dp[y][x] = res
    return res


dp[H][W] = 1
for i in reversed(range(1, H + 1)):
    for j in reversed(range(1, W + 1)):
        #print(i, j)
        if a[i-1][0][j-1] == '#':
            dp[i][j] = 0
        else:
            f(i, j)
print(dp[1][1]%1000000007)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

grid = [None]*n
mod = 10**9+7

for i in range(n):
    grid[i] = list(input())

dp = [[0]*m for _ in range(n)]

dp[0][0] = 1

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

for i in range(m):
    if grid[0][i] != '#':
        dp[0][i] = 1
    else:
        break

for i in range(1, n):
    for j in range(1, m):
        if grid[i][j] == '#':
            continue

        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod

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

Submission status: Accepted

Solution code:
#BFSにdpを乗っける
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w=MI()
lis=[[0]*w for i in range(h)] 
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]=="#":
            lis[i][j]=1
dp=[[0]*w for i in range(h)]
dp[0][0]=1
for i in range(h):
    for j in range(w):
        if lis[i][j]==1:
            continue
        else:
            if i==j==0:
                continue
            if i==0:
                dp[i][j]=dp[i][j-1]
            elif j==0:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
#print(dp)
print(dp[-1][-1]%mod)

Submission status: Accepted

Solution code:
#BFSにdpを乗っける
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w=MI()
lis=[[0]*w for i in range(h)]
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]=="#":
            lis[i][j]=1
#print(lis)
Q=deque([[0,0]])
dp=[[-1]*w for i in range(h)]
dp[0][0]=1
step=[[1,0],[0,1]]
while Q:
    x,y=Q.popleft()
    for i,j in step:
        if x+i>=h or y+j>=w:
            continue
        if lis[x+i][y+j]==1:
            continue
        if dp[x+i][y+j]<0:
            dp[x+i][y+j]=dp[x][y]%mod
            Q.append([x+i,y+j])
        else:
            dp[x+i][y+j]+=dp[x][y]%mod
    #print(dp)
print(max(0,dp[-1][-1])%mod)

Submission status: Accepted

Solution code:


INF = float('inf')
M = 10 ** 9 + 7


def tc():
    h, w = map(int, input().split())
    grid = [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 grid[i][j] == '#':
                continue
            if i > 0:
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % M
            if j > 0:
                dp[i][j] = (dp[i][j] + dp[i][j - 1]) % M

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


tc()

Submission status: Accepted

Solution code:
H,W=list(map(int, input().split()))
G=[['#' for j in range(W+1)]]
for i in range(H):
    G.append(['#']+(list(input())))
# print(G)
C=10**9+7

# dp[i][j]:(i,j)に辿り着く場合の数
# 左や上に壁がないときその場合の数を加算
# 上の行と左の列に壁'#'を追加することにする
# Gだけ1-indexなことに注意

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 G[i+1][j+1]=='#':
            continue
        if G[i][j+1]!='#':
            dp[i][j]+=dp[i-1][j]
            dp[i][j]%=C
        if G[i+1][j]!='#':
            dp[i][j]+=dp[i][j-1]
            dp[i][j]%=C
    # print(dp[i])
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())

mod = 10**9 + 7


def main():

    H, W = in_nn()
    grid = in_map2(H)

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

    for y in range(H):
        for x in range(W):
            if x + 1 < W and grid[y][x + 1]:
                dp[y][x + 1] += dp[y][x]
                dp[y][x + 1] %= mod
            if y + 1 < H and grid[y + 1][x]:
                dp[y + 1][x] += dp[y][x]
                dp[y + 1][x] %= mod

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10**9 + 7
H, W = list(map(int, input().split()))
grid = [[1]*W for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '#':
            grid[h][w] = 0

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

# initialize
dp[0][0] = 1
for h in range(1, H):
    if grid[h][0]:
        dp[h][0] = dp[h-1][0]
for w in range(1, W):
    if grid[0][w]:
        dp[0][w] = dp[0][w-1]

# solve
for h in range(1, H):
    for w in range(1, W):
        if grid[h][w]:
            dp[h][w] = (dp[h-1][w] + dp[h][w-1])%mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
mod = 1000000007
from sys import setrecursionlimit

setrecursionlimit(100000)


def valid(i, j, n, m):
	if 0 <= i < n and 0 <= j < m and good[i][j]:
		return True
	return False


def solve(i, j):
	if dp[i][j] != -1:
		return dp[i][j]
	if i == n - 1 and j == m - 1:
		return 1
	sm = 0
	if valid(i + 1, j, n, m):
		sm += solve(i + 1, j)
	if valid(i, j + 1, n, m):
		sm += solve(i, j + 1)
	dp[i][j] = sm % mod
	return dp[i][j]


n, m = map(int, input().split())
good = [[] for i in range(n)]
for i in range(n):
	s = input()
	for j in range(m):
		if s[j] == '.':
			good[i].append(True)
		else:
			good[i].append(False)

dp = [[-1 for i in range(m)] for j in range(n)]
print(solve(0, 0))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = []
for i in range(n):
    a.append(input())
dp = [[0 for i in range(m)] for j in range(n)]
for i in range(m):
    if a[0][i]=='.':
        dp[0][i]=1
    else:
        break
for i in range(n):
    if a[i][0]=='.':
        dp[i][0]=1
    else:
        break
for i in range(1,n):
    for j in range(1,m):
        if a[i][j]=='.':
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007
print(dp[-1][-1]%1000000007)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


h, w = LI()
s = [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 s[i][j] == "#":
            continue
        if i and s[i-1][j] == ".":
            dp[i][j] += dp[i-1][j]
        if j and s[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:
h,w=map(int,input().split())
grid=[input() for _ in range(h)]
mod=10**9+7
dp=[0]*w
for  i in range(h):
    for j in range(w):
        if i==j==0:
            dp[j]=1
        elif grid[i][j]=='#':
            dp[j]=0
        elif j>0:
            dp[j]=dp[j]+dp[j-1]
print(dp[w-1]%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
mod=10**9+7
m,n=map(int,input().split())
grid=[input() for _ in range(m)]
cache={}
def dp(i,j):
  if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j]=='#':
    return 0
  elif (i,j) in cache:
    return cache[(i,j)]
  elif i==m-1 and j==n-1:
    return 1
  cache[(i,j)]=dp(i+1,j)+dp(i,j+1)
  return cache[(i,j)]

print(dp(0,0)%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
mod=10**9+7
m,n=map(int,input().split())
grid=[list(input()) for _ in range(m)]
cache={}
def dp(i,j):
  if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j]=='#':
    return 0
  elif (i,j) in cache:
    return cache[(i,j)]
  elif i==m-1 and j==n-1:
    return 1
  cache[(i,j)]=dp(i+1,j)+dp(i,j+1)
  return cache[(i,j)]

print(dp(0,0)%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W = IL()
data = SLs(H)

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

for j in range(1,H):
  if data[j][0] != "#":
    dp[j][0] = dp[j-1][0]
for i in range(1,W):
  if data[0][i] != "#":
    dp[0][i] = dp[0][i-1]

for j in range(1,H):
  for i in range(1,W):
    if data[j][i] != "#":
      dp[j][i] = dp[j-1][i] + dp[j][i-1]
      dp[j][i] %= MOD
      
print(dp[-1][-1])

Submission status: Accepted

Solution code:
n , m = map(int , input().split())
dp = []
for i in range(n + 1):
    dp.append([])
    for j in range(m + 1):
        dp[i].append(0)
arr = []
for i in range(n):
    arr.append(input())
dp[1][1] = 1
for i in range(1,n + 1):
    for j in range(1,m + 1):
        if arr[i - 1][j - 1] == '#' or (i == 1 and j == 1):
            continue
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
print(dp[n][m] % 1000000007)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
MOD = 10 ** 9 + 7

grid = [""] * H
for i in range(H):
  grid[i] = input()
  
dp = [[0] * W for i in range(H)]
dp[0][0] = 1
for i in range(H):
  for j in range(W):
    if i + 1 < H and grid[i + 1][j] != "#":
      dp[i + 1][j] += dp[i][j]
      dp[i + 1][j] %= MOD
    if j + 1 < W and grid[i][j + 1] != "#":
      dp[i][j + 1] += dp[i][j]
      dp[i][j + 1] %= MOD
      
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

    
def fun(A,n,m):
    dp = list2d(n,m,0)
    for i in range(1,n): #initialising reachable first row
        if A[i][0]== '.':
            dp[i][0] = 1
        else:
            break
    for j in range(1,m): #initialising reachable first column
        if A[0][j] == '.':
            dp[0][j] = 1
        else:
            break
    dp[0][0] = 1
    for i in range(1,n):
        for j in range(1,m):
            if A[i][j] == "#":
                dp[i][j] = 0
                continue
            if A[i-1][j] == '.':
                dp[i][j] += dp[i-1][j]
                dp[i][j] %= MOD
            if A[i][j-1] == '.':
                dp[i][j] += dp[i][j-1]
                dp[i][j] %= MOD
    return int(dp[n-1][m-1])
        
H,W = ilele()
A = []
for i in range(H):
    B = [*input()]
    A.append(B.copy())
print(fun(A,H,W))

Submission status: Accepted

Solution code:
#import numpy as np
# import math
# import sys
#please work

h,w = map(int, input().split())

l = []
for val in range(h):
    l.append(input())
    
    
ans = [[0 for j in range(w)] for i in range(h)]
#ans = [[0]*w]*
#print(ans)
ans[0][0] =  1

for i in range (h):
    for j in range (w):
        #print(i, j)
        if l[i][j]=="#":
            continue
        if l[i][j] == '.':
            ans[i][j] += (ans[i-1][j] % 1000000007)+(ans[i][j-1] % 1000000007)
print(ans[h-1][w-1] % 1000000007)