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:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(H: int, W: int, a: "List[List[str]]"):
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = 1
    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                dp[h][w] = 1
            elif h == 0:
                if a[h][0][w-1] == ".":
                    dp[h][w] = dp[h][w-1]
            elif w == 0:
                if a[h-1][0][w] == ".":
                    dp[h][w] = dp[h-1][w]
            else:
                if a[h-1][0][w] == "." and a[h][0][w-1] == ".":
                    dp[h][w] = (dp[h-1][w] + dp[h][w-1]) % MOD
                elif a[h-1][0][w] == ".":
                    dp[h][w] = dp[h-1][w]
                elif a[h][0][w-1] == ".":
                    dp[h][w] = dp[h][w-1]
    print(dp[-1][-1])
    return


# Generated by 1.1.6 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(1)]
         for _ in range(H)]  # type: "List[List[str]]"
    solve(H, W, a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
r,c=map(int,input().split())
m=[]
for i in range(r):
    m.append(list(input()))
dp=[[0 for j in range(c)] for i in range(r)]

dp[0][0]=1
for i in range(0,r):
    for j in range(0,c):
        if m[i][j]=='.':
            dp[i][j]+=(dp[i-1][j]+dp[i][j-1])
        

print((dp[r-1][c-1])%(1000000007))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[0]*n
dp=[[0 for i in range (m)]for j in range (n)]
dp[0][0]=1
MOD=int(1e9+7)

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

for i in range (n):
    for j in range (m):
        if a[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[n-1][m-1])

Submission status: Accepted

Solution code:
from sys import stdin


def solve():
    r,c = [int(i) for i in stdin.readline().split()]
    A = []
    for _ in range(r):
        k = str(input())
        l = [1 if i == '.' else '#' for i in k]
        A.append(l)
    pre = False
    for i in range(c):
        if pre: A[0][i] = '#'
        elif A[0][i] == '#': pre = True
    for i in range(1, r):
        for j in range(c):
            if A[i][j] == '#': continue
            elif j == 0: A[i][j] = A[i-1][j]
            elif A[i-1][j] == '#' and A[i][j-1] == '#': A[i][j] = '#'
            elif A[i-1][j] == '#': A[i][j] = A[i][j-1]
            elif A[i][j-1] == '#': A[i][j] = A[i-1][j]
            else: A[i][j] = A[i][j-1] + A[i-1][j]
    if A[-1][-1] == '#': return 0
    else: return A[-1][-1] % ((10**9) + 7)

print(solve())

Submission status: Accepted

Solution code:

MOD = int(1e9)+7
def main():
    H, W = map(int, input().split())
    mat = []
    for i in range(H):
        mat.append(input())

    ways = [[0]*(W+1) for i in range(H+1)]
    ways[0][1] = 1
    for i in range(1, H+1):
        for j in range(1, W+1):
            if mat[i-1][j-1] != '#':
                ways[i][j] = (ways[i-1][j]+ways[i][j-1])%MOD
    print(ways[H][W])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	h, w = IN()
	#s = input()
	map_l = [input() for _ in range(h)]
	l_l = [[0] * w for _ in range(h)]
	l_l[0][0]=1
	for hi in range(h):
		for wi in range(w):
			if map_l[hi][wi] == '#':
				continue
			if wi > 0:
				l_l[hi][wi] += l_l[hi][wi-1]
				l_l[hi][wi] %= mod
			if hi > 0:
				l_l[hi][wi] += l_l[hi-1][wi]
				l_l[hi][wi] %= mod
				
	print(l_l[h-1][w-1])
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
H, W = map(int, input().split(' '))
a = [['0' for _ in range(W + 1)] for _ in range(H + 1)]
dp = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
for i in range(H):
  str_a = input()
  for j in range(W):
     a[i+1][j+1] = str_a[j]
i, j = 1, 1
while i <= H and a[i][1] == '.':
  dp[i][1] = 1
  i += 1
while j <= W and a[1][j] == '.':
  dp[1][j] = 1
  j += 1
for i in range(2, H + 1):
  for j in range(2, W + 1):
    if a[i][j] == '.':
      dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[H][W] % 1000000007)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [list(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 (j != w - 1) and (a[i][j + 1] == '.'):
                dp[i][j + 1] += dp[i][j]
        if (i != h - 1) and (a[i + 1][j] == '.'):
                dp[i + 1][j] += dp[i][j]
print(dp[-1][-1]%(10**9+7))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    m, n = map(int, input().split())
    grid = [input() for _ in range(m)]
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1

    D = [(1, 0), (0, 1)]
    for i in range(m):
        for j in range(n):
            for di, dj in D:
                ni, nj = i + di, j + dj
                if not (0 <= ni < m and 0 <= nj < n):
                    continue
                if grid[ni][nj] == '#':
                    continue
                dp[ni][nj] += dp[i][j]
                if dp[ni][nj] >= MOD:
                    dp[ni][nj] -= MOD

    print(dp[m - 1][n - 1])
resolve()

Submission status: Accepted

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

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

for i in range(1, w):
    if field[0][i] == ".":
        dp[0][i] = dp[0][i-1] 

for i in range(1, h):
    if field[i][0] == ".":
        dp[i][0] = dp[i-1][0]

for row in range(1, h):
    for col in range(1, w):
        if field[row][col] == ".":
            dp[row][col] = (dp[row-1][col] + dp[row][col-1]) % MOD
print(dp[-1][-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a=input().split()
H=int(a[0])
W=int(a[1])
n_list=[[0 for i in range(W)] for i in range(H)]
m_list=[]
for i in range(H) :
  m_list.append(input())

for i in range(H) :
  if m_list[i][0]=='.' :
    n_list[i][0]=1
  else :
    break

for i in range(W) :
  if m_list[0][i]=='.' :
    n_list[0][i]=1
  else :
    break

for i in range(1,H) :
  for j in range(1,W) :
    if m_list[i][j]=='#' :
      n_list[i][j]=0
    else :
      n_list[i][j]=n_list[i-1][j]+n_list[i][j-1]
print(n_list[-1][-1]%(10**9+7))

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
stage = [["#" for x in range(w+2)] for x in range(h+2)]
for i in range(1,h+1):
    stage[i][1:w+1] = list(input())
dp = [[0 for x in range(w+2)] for x in range(h+2)]
dp[1][1] = 1
for j in range(1,h+1):
    for i in range(1,w+1):
        dp[j][i] = dp[j][i]%(10**9+7)
        if(stage[j+1][i] == "."):
            dp[j+1][i] += dp[j][i]
        if(stage[j][i+1] == "."):
            dp[j][i+1] += dp[j][i]
print(dp[h][w])

Submission status: Accepted

Solution code:
mod = 10**9 + 7
H, W = map(int, input().split())
Maze = [[0]*(W+1) for _ in range(H+1)]
Memo = [[0]*(W+1) for _ in range(H+1)]
Memo[H-1][W-1] = 1
for i in range(H):
    S = input()
    for j in range(W):
        Maze[i][j] = S[j]

for a in range(H-1, -1, -1):
    for b in range(W-1, -1, -1):
        if Maze[a][b] == '#':
            Memo[a][b] = 0
        elif (a == H-1) and (b == W-1):
            continue
        else:
            Memo[a][b] = Memo[a+1][b] + Memo[a][b+1]
            Memo[a][b] %= mod
print(Memo[0][0])

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A=[input() for i in range(H)]
d=[[0]*(W+1) for i in range(H+1)]
d[0][1]=1
m=10**9+7
for i in range(H):
    for j in range(W):
        if A[i][j]=='.':
            d[i+1][j+1]=(d[i][j+1]+d[i+1][j])%m
print(d[-1][-1])

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
D = ((1,0),(0,1))

H,W  = LI()
dp = [[0 for _ in range(W+1)] for _ in range(H+1)]
mp = [sys.stdin.readline().rstrip() for _ in range(H)]

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

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

Submission status: Accepted

Solution code:
def cornerval(i, j, a, dp, h, w):

	if a[i][j] == '#':
		return 0
	elif(j== w-1):
		if(dp[i+1][j] == 0):
			return 0
		else:
			return 1
	elif(i==h-1):
		if(dp[i][j+1] == 0):
			return 0
		else:
			return 1

l = 10**9 + 7
h, w = map(int, raw_input().split())
a = []
for i in range(h):
	t= raw_input()
	t = list(t)
	a.append(t)
# print(a)
dp=[[0 for x in range(w)] for x in range(h)]
dp[h-1][w-1] = 1
i=h-1
for j in range(w-2, -1, -1):
	dp[i][j] = cornerval(i, j, a, dp, h, w)
j = w-1
for i in range(h-2, -1, -1):
	dp[i][j] = cornerval(i, j, a, dp, h, w)
dp[h-1][w-1] = 0


for i in range(h-2, -1, -1):
	for j in range(w-2, -1, -1):
		if(a[i][j] == '#'):
			dp[i][j] = 0
		else:
			dp[i][j] = ((dp[i+1][j] % l) + (dp[i][j+1] % l)) % l
# for i in dp:
# 	print(i)
print(dp[0][0])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May  4 15:14:09 2020

@author: Kanaru Sato
"""
import itertools

h,w = list(map(int, input().split()))
mod = 10**9+7
Map = []
for i in range(h):
    Map.append(list(input()))

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

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            dp[i][j] = 1
        else:
            if Map[i][j] == "#":
                dp[i][j] = -1
            else:
                if i-1 >= 0 and dp[i-1][j] != -1:
                    dp[i][j] += dp[i-1][j]
                if j-1 >= 0 and dp[i][j-1] != -1:
                    dp[i][j] += dp[i][j-1]
                dp[i][j] %= mod

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

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys, bisect, math, itertools
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

h, w = inpl()
maze = [list(input())[:-1] 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 i == 0 and j == 0:
            continue
        left = dp[i][j-1] if j-1>=0 and maze[i][j-1] == "." else 0
        up = dp[i-1][j] if i-1>=0 and maze[i-1][j] == "." else 0
        dp[i][j] = left + up
print(dp[h-1][w-1] % mod)
# print(dp)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]

MOD = 10 ** 9 + 7
dp = [[0] * w for _ in range(h)]

i = 0
while i < w and grid[0][i] != '#':
	dp[0][i] = 1
	i += 1

j = 0
while j < h and grid[j][0] != '#':
	dp[j][0] = 1
	j += 1

for i in range(1, h):
	for j in range(1, w):
		if grid[i][j] == '#':
			dp[i][j] == 0
		else:
			dp[i][j] = dp[i - 1][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())
maze=[tuple(input()) for _ in range(h)]
dp=[[0]*w for _ in range(h)]
mod=10**9+7
dp[0][0]=1
for y in range(h):
  for x in range(w):
    if maze[y][x]=='#':
      dp[y][x]=0
    else:
      if y>0:
        dp[y][x]+=dp[y-1][x]
      if x>0:
        dp[y][x]+=dp[y][x-1]
      dp[y][x]%=mod
print(dp[-1][-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w = na()
a = nsn(h)

dp = [[0] * (w + 1) for _ in range(h + 1)]
dp[1][1] = 1
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            dp[i + 1][j + 1] += dp[i][j + 1] + dp[i + 1][j]

print(dp[h][w] % mod)

Submission status: Accepted

Solution code:
#F
H,W=map(int,input().split())
A=[[x for x in input()] for i in range(H)]
mod=10**9+7

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

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

print(dp[0][0])

Submission status: Accepted

Solution code:
mod = 10**9+7
h,w = map(int,input().split())
grid = [[l == "#" for l in list(input())] for _ in range(h)]
dp = [[0]*w for _ in range(h)]
dp[0][0] = 1
for s in range(1,h+w):
  for i in range(max(0,s-w+1),min(h,s+1)):
    j = s-i
    if grid[i][j]:
      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][j-1]+dp[i-1][j])%mod
print(dp[-1][-1]%mod)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
p=10**9+7
ma=[]
dp=[[0]*(W+2) for j in range(H+2)]
an=[]
dp[1][1]=1
for i in range(H):
     ma.append(list(input()))
     for j in range(W):
         if i==j==0:
             continue
         if ma[i][j]=="#":
             dp[i + 1][j + 1]=0
         else:
             dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j])%p
print(dp[H][W])
#print(tin[an.index(ans)])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

M = 10 ** 9 + 7
H, W = map(int, readline().split())
grid = []
for i in range(H):
    grid.append(readline().decode("utf-8").rstrip())
    assert len(grid[-1]) == W


def solve():
    t = [0] * W
    t[0] = 1
    for c in range(1, W):
        if grid[0][c] == ".":
            t[c] = t[c - 1]
    for r in range(1, H):
        for c in range(W):
            if grid[r][c] == "#":
                t[c] = 0
            elif c > 0:
                t[c] += t[c - 1]
                t[c] %= M
        # print(r, "\t", t)
    return t[-1]


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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

grid=[]

m=10**9+7

for i in range(H):
    a= list(input())
    grid.append(a)

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

for i in reversed(range(H)):
    for j in reversed(range(W)):
        dp[i][j] = dp[i+1][j] + dp[i][j+1]
        dp[H-1][W-1]=1
        if grid[i][j]=="#":
            dp[i][j]=0
print(dp[0][0]%m)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
h, w = map(int, input().split())
grid = '#' * (w + 2)
for _ in range(h):
    grid += '#' + input() + '#'
grid += '#' * (w + 2)
D = [0] * len(grid)
start = w + 3
goal = -(w + 4)
D[start] = 1
for i in range(start + 1, len(grid)):
    if grid[i] == '#':
        continue
    D[i] = (D[i - 1] + D[i - (w + 2)]) % MOD
print(D[goal])

Submission status: Accepted

Solution code:
from collections import deque

MOD = 10 ** 9 + 7
h, w = map(int, input().split())
grid = '#' * (w + 2)
for _ in range(h):
    grid += '#' + input() + '#'
grid += '#' * (w + 2)
D = [0] * len(grid)
start = w + 3
goal = -(w + 4)
D[start] = 1
for i in range(start + 1, len(grid)):
    if grid[i] == '#':
        continue
    D[i] = (D[i - 1] + D[i - (w + 2)]) % MOD
print(D[goal])

Submission status: Accepted

Solution code:
n,m=map(int,raw_input().split())
a=[list(raw_input().strip()) for _ in xrange(n)]
z=[[0]*(m+1) for _ in xrange(n+1)]
z[0][1]=1
for i in xrange(n):
    for j in xrange(m):
        if a[i][j]=='.':
            z[i+1][j+1]+=z[i+1][j]+z[i][j+1]
print z[-1][-1]%(pow(10,9)+7)

Submission status: Accepted

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

dp = [0]*(w+1)
dp[1] = 1
for i in grid:
    newdp = dp[:]
    for j, k in enumerate(i):
        newdp[j+1] = dp[j+1] + newdp[j] if k=='.' else 0
    dp = newdp
print(dp[-1]%(10**9+7))

Submission status: Accepted

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

dp = [[0]*W for i in range(H)]
mod = 10**9 + 7
dp[0][0] = 1

for i in range(H):
    for j in range(W):
        if a[i][j] == '#':
            continue
        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[-1][-1])

Submission status: Accepted

Solution code:
import numpy as np

H,W = map(int,input().split())
A = list()
for i in range(H):
    A.append(list(input()))
dp = [[0]*(W) for i in range(H)]
dp[0][0] = 1

for i in range(H):   
    for j in range(W):
        if A[i][j] == '.':
            # 横が行けるかどうか
            try:
                if A[i][j+1] == '.':
                    dp[i][j+1] += dp[i][j]
            except IndexError as e:
                # print('IndexError')
                pass
            # 縦が行けるかどうか
            try:
                if A[i+1][j] == '.':
                    dp[i+1][j] += dp[i][j]
        
            except IndexError as e:
                # print('IndexError')
                pass

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

Submission status: Accepted

Solution code:
import itertools

MOD = 10 ** 9 + 7

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][1] = 1

it = itertools.product(range(H), range(W))
next(it)
for h, w in it:
    if A[h][w] == '.':
        dp[h + 1][w + 1] = (dp[h][w + 1] + dp[h + 1][w]) % MOD
print(dp[H][W])

Submission status: Accepted

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

grid = [[0]*W for h in range(H)]
grid[0][0] = 1

for h in range(H) :  
  row = raw_input()

  for w in range(W) :
    if row[w] == '#' : continue
    if h > 0 : grid[h][w] += grid[h-1][w]
    if w > 0 : grid[h][w] += grid[h][w-1]
    grid[h][w] %= MOD
  
print grid[-1][-1] % MOD

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
p = 10**9+7
S = [input() for i in range(h)]
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 and S[i-1][j] == '.':
            DP[i][j] += DP[i-1][j]
        if j > 0 and S[i][j-1] == '.':
            DP[i][j] += DP[i][j-1]
        DP[i][j] %= p
print(DP[h-1][w-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy

MODULO = pow(10, 9) + 7


def solve_matrix(values, h, w):
    dp = [[0] * (1 + w) for _ in range(1 + h)]
    dp[1][1] = 1
    for i in range(h):
        for j in range(w):
            if i + j != 0 and values[i][j] == ".":
                LOG.debug((i, j, values[i][j]))
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j]) % MODULO
    LOG.debug("\n".join(map(str, dp)))
    return dp[h][w]


def solve(values, h, w):
    dp = [0] * w
    dp[0] = 1
    for i in range(h):
        # LOG.debug((dp))
        prev = dp.copy()
        dp = [0] * w
        for j in range(w):
            # LOG.debug((i, j, values[i][j]))
            if i + j == 0:
                dp[j] = 1
                continue
            if values[i][j] == "#":
                # LOG.debug(("skipped"))
                continue
            if j != 0:
                dp[j] = (dp[j] + dp[j - 1]) % MODULO
            dp[j] = (dp[j] + prev[j]) % MODULO
    LOG.debug((dp))
    return dp[w - 1]


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    H, W = map(int, input().split())
    values = []
    for _ in range(H):
        values.append(input())
    # result = solve_matrix(values, H, W)
    result = solve(values, H, W)
    print(result)


def configure_log():
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [0]*(H+1)
S[0] = '*'*(W+1)
for h in range(1,H+1):
    S[h] = '*' + input()

dps = [[0]*(W+1) for _ in range(H+1)]
mod = 10**9+7

def dp(h,w):
    if h==1 and w==1:
        return 1
    if S[h][w]=='.':
        return (dps[h-1][w]+dps[h][w-1])%mod
    return 0


def solve():
    for h in range(1,H+1):
        for w in range(1,W+1):
            dps[h][w] = dp(h,w)
    ans = dps[-1][-1]
    return ans
print(solve())

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(1e9)
mod=int(1e9)+7


n,m=mdata()
matrix = [data() for i in range(n)]
dp=[[0]*m for i in range(n)]
if matrix[0][0]!='#':
    dp[0][0]=1
for i in range(n):
    for j in range(m):
        if matrix[i][j]=='#':
            continue
        if i>0:
            dp[i][j]=(dp[i][j]+dp[i-1][j])%mod
        if j>0:
            dp[i][j]=(dp[i][j]+dp[i][j-1])%mod
print((dp[-1][-1])%mod)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
a = [readline().rstrip().decode() for _ in range(h)]
dp = [[0] * w for _ in range(h)]
mod = 10 ** 9 + 7
dp[0][0] = 1

for i in range(h):
    for j in range(w):
        if a[i][j] != '#':
            if i != h - 1:
                if a[i + 1][j] != '#':
                    dp[i + 1][j] += dp[i][j]
                    dp[i + 1][j] %= mod
            if j != w - 1:
                if a[i][j + 1] != '#':
                    dp[i][j + 1] += dp[i][j]
                    dp[i][j + 1] %= mod
print(dp[-1][-1] % mod)

Submission status: Accepted

Solution code:

def solve(H, W, grid):
	MOD = 10 ** 9 + 7
	dp = [0] * (W)
	for j in range(W):
		if grid[0][j] == '#':
			break
		if j == 0:
			dp[j] = 1
		else:
			dp[j] = dp[j-1]

	for i in range(1, H):
		dp2 = [0] * W
		dp2[0] = dp[0] if grid[i][0] != '#' else 0
		for j in range(1, W):
			dp2[j] = dp[j] + dp2[j-1] if grid[i][j] != '#' else 0
		dp = dp2

	return dp[-1] % MOD

H, W = [int(s) for s in input().split()]
grid = []
for _ in range(H):
	grid.append([s for s in input()])
print(solve(H, W, grid))

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 i in range(1, H + 1):
    for j in range(1, W + 1):
        if A[i - 1][j - 1] == ".":
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())
ans = [[0 for _ in range(w)] for _ in range(h)]
ans[0][0] = 1
mod = 7+10**9
for i in range(h):
    for j in range(w):
        if ans[i][j] == 0 or l[i][j] == "#":
            continue
        if i+1 < h:
            ans[i+1][j] += ans[i][j]
            ans[i+1][j] %= mod
        if j+1 < w:
            ans[i][j+1] += ans[i][j]
            ans[i][j+1] %= mod
print(ans[-1][-1])