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:
H,W = [int(v) for v in input().split()]
arr = [input() for _ in range(H)]
     
dp = [[0 for _ in range(W+1)] for _ in range(H+1)]
dp[1][1] = 1
dp = [[0 for _ in range(W+1)] for _ in range(H+1)]
dp[1][1] = 1
     
#print(dp)
for h,row in enumerate(arr,1):
        for w,cell in enumerate(row,1):
            if cell != '#':
                dp[h][w] += int((dp[h-1][w] + dp[h][w-1]) % (1e9 + 7))
    
print(dp[-1][-1])

Submission status: Accepted

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

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

for h,row in enumerate(area,1):
    for w,cell in enumerate(row,1):
        if cell != '#':
            dp[h][w] += int((dp[h-1][w] + dp[h][w-1]) % (1e9 + 7))

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

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
Root = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    String = input()
    for j in range(W):
        Root[i][j] = String[j]
if Root[0][0] == '.':
    Grid = [[0 for i in range(W+1)] for j in range(H+1)]
for i in range(H):
    for j in range(W):
        if Root[i][j] == '.':
            if i == 0 and j == 0:
                Grid[1][1] = 1
            else:
                Grid[i+1][j+1] = Grid[i+1][j] + Grid[i][j+1]
        else:
            Grid[i+1][j+1] = 0
print(Grid[H][W] % 1000000007)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

H, W = mi()
A = [input() for i in range(H)]

dp = dp2(float("inf"), W, H)
dp[0][0] = 1
INF = 10**9+7

for i in range(H):
    for j in range(W):
        if i==0 and j == 0:
            dp[0][0] = 1
            continue
        if A[i][j] == '.':
            dp[i][j] = 0
            if i > 0 and A[i-1][j] == '.':
                dp[i][j] = (dp[i][j] + dp[i-1][j]) % INF
            if j > 0 and A[i][j-1] == '.':
                dp[i][j] = (dp[i][j] + dp[i][j-1]) % INF

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10**9+7
H, W = map(int, input().split())
G = [input() for i in range(H)]
dp = [[0]*W for i in range(H)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if G[i][j] == '.':
            if i - 1 >= 0:
                if j - 1 >= 0:
                    dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod
                else:
                    dp[i][j] = dp[i-1][j]
            elif j - 1 >= 0:
                dp[i][j] = dp[i][j-1]
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

h,w = map(int,readline().split())
maze = []
for _ in range(h):
	maze.append(readline().rstrip().decode('utf-8'))

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] == "#":
			continue
		if i > 0:
			dp[i][j] += dp[i-1][j]
		if j > 0:
			dp[i][j] += dp[i][j-1]
		dp[i][j]%=10**9+7

print(dp[-1][-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
MOD = 10**9 + 7
for y in range(0, H):
    for x in range(0, W):
        if A[y][x] == '#':
            continue

        if x - 1 >= 0:
            dp[y][x] += dp[y][x-1]
            dp[y][x] %= MOD
        if y - 1 >= 0:
            dp[y][x] += dp[y-1][x]
            dp[y][x] %= MOD
# print(*dp, sep='\n')
print(dp[-1][-1])

Submission status: Accepted

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

div = 10**9+7

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


for y in range(H):
    for x in range(W):
        if x + 1 < W and field[y][x+1] != '#':
            patterns[y][x+1] += patterns[y][x] % div
        if y + 1 < H and field[y+1][x] != '#':
            patterns[y+1][x] += patterns[y][x] % div

print(patterns[-1][-1] % div)

Submission status: Accepted

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


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


H, W = map(int, input().split())

data = [[None] * (W+1) for i in range(H+1)]
dp = [[0] * (W+1) for i in range(H+1)]

dp[0] = [0] * (W+1)

for i in range(H):
    temp = list(input())
    dp[i + 1][0] = 0
    for j in range(W):
        data[i + 1][j + 1] = temp[j]


for i in range(1, H + 1):
    for j in range(1, W + 1):
        if (i == 1) and (j == 1):
            dp[i][j] = 1
            continue

        if data[i][j] == '.':
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        else:
            dp[i][j] = 0

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

Submission status: Accepted

Solution code:
def solve(n, m, grid):
    dp = [[0] * (m+1) for _ in range(n+1)]
    dp[1][1] = 1
    mod = int(1e9+7)

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

    return dp[-1][-1]


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, m = inp()
    grid = [input() for _ in range(n)]
    print(solve(n, m, grid))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
#G=[[-1 if input() else 0 for i in range(W)] for _ in range(H)]
MOD=10**9+7
#リストver
dp=[[-1]*W for _ in range(H)]
for i in range(H):
    s=input()
    for j in range(W):
        if s[j]=='#':
            dp[i][j]=0
dp[0][0]=1

'''
#numpy ver
import numpy as np
dp=np.array([list(input()) for _ in range(H)])

dp=np.where(dp=='.',-1,dp)
dp=np.where(dp=='#',0,dp)

dp[0][0]=1
'''
for i in range(H):
    for j in range(W):
        if dp[i][j]==-1:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
            elif i>=1 and j==0:
                dp[i][j]=dp[i-1][j]
            elif i==0 and j>=1:
                dp[i][j]=dp[i][j-1]

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

Submission status: Accepted

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

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

DP[0][0] = 1

mod = 10**9 + 7

for i in range(H):
    for j in range(W):
        if S[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:
e=10**9+7
n,m=map(int,input().split())
l=[]
for i in range(n):
    l.append(input())
dp=[]
for i in range(n):
    dp.append([0]*m)

dp[-1][-1]=1
for i in range(m-2,-1,-1):
    if l[n-1][i]=='#':
        pass
    else:
        dp[n-1][i]+=dp[n-1][i+1]
for i in range(n-2,-1,-1):
    if l[i][m-1]=='#':
        pass
    else:
        dp[i][m-1]+=dp[i+1][m-1]
for i in range(n-2,-1,-1):
    for j in range(m-2,-1,-1):
        if l[i][j]=='#':
            pass
        else:
            dp[i][j]=(dp[i][j+1]+dp[i+1][j])%e
print(dp[0][0])

Submission status: Accepted

Solution code:
mod = 10**9+7
h,w = map(int, input().split())

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

dp[0][0] = int(a[0][0] == '.')

for i in range(1,h):
    dp[i][0] = int(a[i][0] == ".")*dp[i-1][0]
for j in range(1,w):
    dp[0][j] = int(a[0][j] == ".")*dp[0][j-1]

for i in range(1, h):
    for j in range(1, w):
        dp[i][j] = int(a[i][j] == '.') * (dp[i - 1][j] + dp[i][j - 1])
        dp[i][j] %= mod
# for i in dp:
#     print(*i)

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [[1] * (W + 2)]
for _ in range(H):
    tmp = list(input())
    tmp = [1] + [0 if t == '.' else 1 for t in tmp] + [1]
    A.append(tmp)
A += [[1] * (W + 2)]

MOD = 10**9 + 7

dp = [[0] * (W + 2) for _ in range(H + 2)]
dp[H][W] = 1
# dp[H][W]
# dp[i][j] : (i, j)マスから(H, W)マスへいくのに通れる経路の数
# dp[i][j] : dp[i + 1][j] + dp[i][j + 1] ?
for i in range(H + 1, 0, -1):
    for j in range(W + 1, 0, -1):
        if A[i][j] == 0:
            dp[i][j] = (dp[i][j] + dp[i + 1][j] + dp[i][j + 1]) % MOD
ans = dp[1][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 9)

def main():
    H,W = map(int,input().split())
    s = [list(input()) for _ in range(H)]
    MOD = 10**9+7
    
    memo = [[-1 for _ in range(W)] for _ in range(H)]
    memo[0][0] = 1
    def ch(x,y):
        if memo[x][y] != -1:
            return memo[x][y]
        else:
            ret = 0
            if x == 0:
                if s[x][y-1] == ".":
                    ret += ch(x,y-1)
            elif y == 0:
                if s[x-1][y] == ".":
                    ret += ch(x-1,y)
            else:
                if s[x][y-1] == ".":
                    ret += ch(x,y-1)
                if s[x-1][y] == ".":
                    ret += ch(x-1,y)
            ret %= MOD
            memo[x][y] = ret
            return ret
    
    ch(H-1,W-1)
    print(memo[-1][-1]%MOD)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

H, W = MAP()
a = ["#"*(W+2)]+["#"+input()+"#" for _ in range(H)] + ["#"*(W+2)]

dx = [1, 0]
dy = [0, 1]

comb = [[0]*(W+2) for _ in range(H+2)]
comb[1][1] = 1
q = deque()
q.append((1, 1))
while q:
    i, j = q.popleft()
    for k in range(2):
        y = i+dy[k]
        x = j+dx[k]
        if a[y][x] != "#":
            if comb[y][x] == 0:
                q.append((y, x))
            comb[y][x] = (comb[y][x] + comb[i][j])%mod

print(comb[H][W])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
H,W=map(int,input().split())

A=[]
for _ in range(H):
    A.append(list(input()))

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

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

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

Submission status: Accepted

Solution code:
MOD = 10**9+7
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
	for j in range(w):
		if (i == 0) & (j == 0):
			dp[i][j] = 1
		elif a[i][j] == '#':
			continue
		elif 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[h-1][w-1])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

H, W = map(int, input().split())
count = [0] * W

row = input()
for w in range(W):
  if row[w] == '#':
    break
  else:
    count[w] = 1

for h in range(1, H):
  row = input()
  if row[0] == '#':
    count[0] = 0
  for w in range(1, W):
    if row[w] == '#':
      count[w] = 0
    else:
      count[w] = (count[w-1] + count[w]) % MOD
print(count[-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)]

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

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

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]
MOD = 10**9 + 7

d = deque([[0,0]])
n_pattern = [[0]*W for _ in range(H)]
n_pattern[0][0] = 1

while d:
    y, x = d.popleft()
    for new_y, new_x in ([int(y)+1, int(x)], [int(y), int(x)+1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and a[new_y][new_x] == ".":
            if n_pattern[new_y][new_x] > 0:
                once_updated_flg = 1
            else:
                once_updated_flg = 0
            n_pattern[new_y][new_x] += n_pattern[y][x]
            n_pattern[new_y][new_x] %= MOD
            if once_updated_flg == 0:
                d.append([new_y, new_x])

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

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
l = [list(input()) for i in range(h)]
dp = [[0 for i in range(w)] for i in range(h)]
dp[0][0] = 1
mod = 10**9+7

for i in range(h):
    for j in range(w):
        if i+1<h and l[i+1][j] != "#":
            dp[i+1][j] = (dp[i][j]+dp[i+1][j])%mod
        if j+1 < w and l[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:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
h,w = mi()
a = [list(input()) for _ in range(h)]

dp = [[0]*w for i in range(h)]
dp[0][0] = 1
for i in range(1,w):
    if a[0][i] == '#':break
    dp[0][i] = 1
for i in range(1,h):
    if a[i][0] == '#':break
    dp[i][0] = 1

for i in range(1,h):
    for j in range(1,w):
        if a[i][j] == '#':continue
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
mod = 10**9+7
print(dp[h-1][w-1]%mod)

Submission status: Accepted

Solution code:
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 10**9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n,m = li()
l = []

for i in range(n):l.append(li2())
l[0][0] = 1


for i in range(1,n):l[i][0] = 1*l[i-1][0] if l[i][0] != '#' else 0

for j in range(1,m):l[0][j] = 1*l[0][j-1] if l[0][j] != '#' else 0

for i in range(1,n):
    for j in range(1,m):
        if l[i][j] != '#':
            l[i][j] = l[i-1][j] + l[i][j-1]
        else:l[i][j] = 0
        l[i][j]%=mod

print(l[-1][-1])

Submission status: Accepted

Solution code:
R, C = tuple(map(int, input().split()))
grid = [list(input()) for _ in range(R)]
dp = [[0 for _ in range(C)] for _ in range(R)]
for row in range(R):
    if grid[row][0] != '#':
        dp[row][0] = 1
    else:
        break

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





def gridpaths(R, C, grid, MAX=10 ** 9 + 7):
    for row in range(1, R):
        for col in range(1, C):
            if grid[row][col] != '#':
                dp[row][col] = (dp[row - 1][col] + dp[row][col - 1])%MAX
        # print(dp)
    return dp[-1][-1]


print(gridpaths(R, C, grid))

Submission status: Accepted

Solution code:
MOD=10**9+7
H,W=map(int,input().split())
G=[input() for i in range(H)]
dp=[[0]*W for i in range(H)]
dp[0][0]=1

for i in range(H):
    for j in range(W):
        if(G[i][j]=='#'):
            continue
        if(i+1<H and G[i+1][j]!='#'):
            dp[i+1][j]=(dp[i+1][j]+dp[i][j])%MOD
        if(j+1<W and G[i][j+1]!='#'):
            dp[i][j+1]=(dp[i][j+1]+dp[i][j])%MOD
print(dp[H-1][W-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[0]*W for i in range(H)]

cnt=0
for i in range(H):
  if A[i][0]=='.' and cnt==0:
    D[i][0]=1
  else:
    cnt=1
cnt=0
for i in range(W):
  if A[0][i]=='.' and cnt==0:
    D[0][i]=1
  else:
    cnt=1
mod=10**9+7
for i in range(1,H):
  for j in range(1,W):
    if A[i][j]=='.':
      D[i][j]+=(D[i-1][j]+D[i][j-1])
      D[i][j]%=mod
print(D[-1][-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
grd=[[0 for i in range(y)] for i in range(x)]
for i in range(x):
    s=input()
    for j in range(len(s)):
        if(s[j]=='.'):
            grd[i][j]=0
        else:
            grd[i][j]=-1

            
dp=[[0 for i in range(y)] for i in range(x)]
vi=[[0 for i in range(y)] for i in range(x)]
dp[0][0]=1
def grid(i,j):
    if(i==0 and j==0):
        return 1;
    if(i>=x or j>=y):
        return 0;
    if(grd[i][j]==-1):    
        return 0;
    if(vi[i][j]):
        return dp[i][j]
    vi[i][j]=1
    dp[i][j]=((dp[i-1][j])%(10**9+7)+dp[i][j-1]%(10**9+7))%(10**9+7)
    return dp[i][j];
for i in range(x):
    for j in range(y):
        dp[i][j]=grid(i,j)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
MOD = 10**9+7
dp = [[0]*1100 for _ in range(1100)]
H, W = input_nums()
a = []
for i in range(H):
    a.append(input())

dp[0][0] = 1
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+1][j] + dp[i][j]) % MOD
        if j+1 < W and a[i][j+1] == '.':
            dp[i][j+1] = (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())
#field = [list(input()) for _ in range(H)]
field = []
for _ in range(H):
    tmp = list(input())
    tmp.append("#")
    field.append(tmp)
field.append(["#"] * (W))
dp = [[0] * (W+1) for _ in range(H+1)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            continue
        # 配り先のマスを見て、回数を増やせるか判定
        if field[h+1][w] == ".":
            dp[h+1][w] += dp[h][w]
            dp[h+1][w] %= mod
        if field[h][w+1] == ".":
            dp[h][w+1] += dp[h][w]
            dp[h][w+1] %= mod

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

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(1000000)
dp = [[0]*(1000+1) for x in range(1000+1)]
tab = []
def main():
    global n,m
    n,m = map(int,input().split())
    
    for x in range(n):
        tab.append(input())
    x = 0
    while x < n and tab[x][0] != "#":
        dp[x][0] = 1
        x += 1
    x = 0
    while x < m and tab[0][x] != "#":
        dp[0][x] = 1
        x += 1
    for x in range(1,n):
        for y in range(1,m):
            if tab[x][y]!="#":
                dp[x][y] = dp[x][y-1] + dp[x-1][y]
    
    print(dp[n-1][m-1]%(10**9+7))
main()

Submission status: Accepted

Solution code:
h,w = map(int, input().split())

bignum = pow(10,9) + 7

mee = [[0 for i in range(w+1)] for j in range(h)]
#starting should all be 1
#walled = -1

for j in range(h):
    mee[j][0] = 0


for i in range(h):
    temp = input()
    for j in range(w):
        if temp[j] == "#":
            mee[i][j+1] = -1

for i in range(w+1):
    if mee[0][i] == -1:
        break
    mee[0][i] = 1

#from top and from left >0 --> +1
#
for i in range(1,h):
    for j in range(1,w+1):
        if mee[i][j] == -1:
            continue
        if mee[i - 1][j] > 0 and mee[i][j - 1] > 0:
            mee[i][j] = mee[i - 1][j] % bignum + mee[i][j - 1] %bignum

        elif mee[i - 1][j] > 0 or mee[i][j - 1] >0:
            mee[i][j] = max(mee[i-1][j],mee[i][j-1])

print(mee[-1][-1] % bignum)

Submission status: Accepted

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

dp = [[0 for i in range(W)] for j in range(H)]
dp[0][0] = 1
mod = int(1e9) + 7
for i in range(H):
    for j in range(W):
        if i > 0 and mark[i - 1][j] == '.':
            dp[i][j] += dp[i - 1][j] % mod
        if j > 0 and mark[i][j - 1] == '.':
            dp[i][j] += dp[i][j - 1] % mod
        dp[i][j] %= mod

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

Submission status: Accepted

Solution code:
inp = list(map(lambda x: int(x), input().split(" ")))
H = inp[0]
W = inp[1]

LIM = 10**9 + 7

field = [""]*H

for i in range(H):
    field[i] = input()

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

dp[H-1][W-1] = 1

for i in range(H):
    for j in range(W):
        n = 0
        if(field[H-1-i][W-1-j] != "#"):
            if(H-i<H):
                n += dp[H-i][W-1-j]
            if(W-j<W):
                n += dp[H-1-i][W-j]
            if (n>0):
                if (n>=LIM):
                    n -= LIM
                dp[H-1-i][W-1-j] = n

print(dp[0][0])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
ans = [[0 for i in range(W)] for j in range(H)]
mark = []
for i in range(H):
    mark.append(input())

ans[0][0] = 1
mod = 10**9 + 7
for i in range(H):
    for j in range(W):
        if mark[i][j] == '#':
            continue
        if i > 0:
            ans[i][j] += ans[i-1][j]
        if j > 0:
            ans[i][j] += ans[i][j-1]
        ans[i][j] %= mod

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

Submission status: Accepted

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

dp = [[0] * w for i in range(h)]
# 下の2つのfor で初期化をしている。ここで # が出たらそれ以降はいけないことに注意。(break)
for i in range(h):
    if f[i][0] != "#":
        dp[i][0] = 1
    else:
        break

for i in range(w):
    if f[0][i] != "#":
        dp[0][i] = 1
    else:
        break

for x in range(1, h):
    for y in range(1, w):
        if f[x][y] == ".":
            dp[x][y] = dp[x-1][y]+dp[x][y-1]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2<<28)

h, w = [int(i) for i in input().split()]
g = [list(input()) for _ in range(h)]
MOD = 10**9 + 7


def dfs(y, x):
    if not (0 <= y < h and 0 <= x < w):
        return 0
    elif g[y][x] == "#":
        return 0
    elif y == h - 1 and x == w - 1:
        return 1
    elif isinstance(g[y][x], int):
        return g[y][x]
    else:
        ret = 0
        for dy, dx in ((1, 0), (0, 1)):
            ret += dfs(y+dy, x+dx) % MOD
            ret %= MOD
        ret %= MOD
        g[y][x] = ret
        return ret


print(dfs(0, 0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def rr(): return sys.stdin.readline().rstrip()
def rri(): return int(rr())
def rrl(): return list(map(int, rr().split()))
def rrt(): return tuple(map(int, rr().split()))
def rrle(): return (line.rstrip() for line in sys.stdin.readlines())
def rrtl(): return [tuple(map(int, l.split())) for l in rrle()]
from collections import defaultdict
def mus(d=lambda: 0): return defaultdict(lambda: defaultdict(d))
def dd0(d=lambda: 0): return defaultdict(d)
def ms(x, y, d=0): return [[0]*y for i in range(x)]
def ar(x, d=0): return [d]*x
def ppm(m, n=0, x=0, y=0): print("\n".join(("\t".join((str(m[j][i]) for j in range(y or n))) for i in range(x or n))))
def ppa(a, n): print("\t".join(map(str, a[0:n])))
def ppl(a=0, x=[1]): x[0]=a or (x[0]+1); print("-"+"- -"*14+"-# "+str(x[0]-2)+" #-"+"- -"*14+"-")
def fltn(a): (i for sub in a for i in sub)
def yn(x): return "YES" if x else "NO"
from itertools import accumulate
from itertools import groupby
def grp(x): return ((i, sum(1 for _ in g)) for i, g in groupby(x))
import math
#def rnar(): return (*rrl(), rrl())
#def rn(): return (*rrl(),)
def dpp(a, b=""): print("#| {} |#:^ {} ^:".format(a, b))

def read():
    h, w = rrl()
    return (h, w, list(rrle()),)

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

    for i in range(1, h):
        for j in range(1, w):
            if field[i][j] == ".":
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % (10**9 + 7)
    ans = dp[-1][-1]
    return ans

if __name__ == "__main__":
    #test_count = rri()
    test_count = 1
    for _ in range(test_count):
        input_data = read()
        result = solve(*input_data)
        print(result)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

maze = []
for i in range(h):
    maze.append(input().rstrip())

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

mod = 10**9 + 7

for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            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])

Submission status: Accepted

Solution code:
h, w = map(int,input().split())
MOD = 10**9+7
grid = []
grid.append('#' * (w+2))
for _ in range(h):
    grid.append('#' + input().rstrip() + '#')
grid.append('#' * (w+2))
            
dp=[[0] * (w+2) for _ in range(h+2)]
dp[1][1] = 1
for i in range(1, h+1):
    for j in range(1, w+1):
        if grid[i][j] == "#":
            continue
        if i == 1 and j == 1:
            continue
        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD
print(dp[h][w] % MOD)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
grid = [list(input()) for _ in range(H)]
#print(grid)
MOD = 10**9+7
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[H-1][W-1])

Submission status: Accepted

Solution code:
r,c=list(int(i) for i in input().split())
#
za=10**9+7
A=[]
for i in range(r):
	B=input()
	k=list(B)
	A.append(k)
dp=[[0 for i in range(c+1)]for j in range(r+1)]
if A[r-1][c-1]=="#":
	dp[r-1][c-1]=0
else:
	dp[r-1][c-1]=1
for i in range(r-1,-1,-1):
	for j in range(c-1,-1,-1):
		if A[i][j]!="#":
			if(i<r-1 and j<c-1):
				if A[i+1][j]=="#" and A[i][j+1]!='#':
					dp[i][j]=dp[i][j+1]
				elif A[i+1][j]!="#" and A[i][j+1]=='#':
					dp[i][j]=dp[i+1][j]
				elif A[i+1][j]!="#" and A[i][j+1]!="#":
					dp[i][j]=dp[i+1][j]+dp[i][j+1]
			elif j==c-1 and i!=r-1:
				if A[i+1][j]!="#":
					dp[i][j]=dp[i+1][j]
			elif(i==r-1 and j!=c-1):
				if A[i][j+1]!="#":
					dp[i][j]=dp[i][j+1]


print(dp[0][0]%za)