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 = map(int, input().split())
A = [input() for _ in range(H)]

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 A[i][j] == '#':
            continue
        if i < 1 or A[i-1][j] == '#':
            pass
        else:
            dp[i][j] += dp[i-1][j]
        if j < 1 or A[i][j-1] == '#':
            pass
        else:
            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())
c=[]
for i in range(h):
  c+=[list(input())]
d=[[0 for i in range(w)]for j in range(h)]
d[0][0]=1
for i in range(1,w):
  d[0][i]=d[0][i-1]*(c[0][i]=='.')
for i in range(1,h):
  d[i][0]=d[i-1][0]*(c[i][0]=='.')
for i in range(1,h):
  for j in range(1,w):
    d[i][j]=(d[i][j-1]+d[i-1][j])*(c[i][j]=='.')
print(d[-1][-1]%(10**9+7))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = []
mod = 10**9
mod += 7
# print(mod)
for h in range(H):
	A.append(list(input()))
dp = [[0 for w in range(W)] for h in range(H)]
dp[0][0] = 1
for i in range(H):
	for j in range(W):
		if A[i][j] != "#":
			if i > 0 and A[i-1][j] != '#':
				dp[i][j] = (dp[i][j]%mod + dp[i-1][j]%mod)%mod
			if j > 0 and A[i][j-1] != '#':
				dp[i][j] = (dp[i][j]%mod + dp[i][j-1]%mod)%mod
# print(dp)
print(dp[H-1][W-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    mod = 10**9+7
    H,W = list(map(int,input().split()))
    grid = [list(input()) for i in range(H)]
    DP = [[0]*W for i in range(H)]
    for i in range(H):
        if grid[i][0] == '.':
            DP[i][0] = 1
        else:
            break
    for i in range(W):
        if grid[0][i] == '.':
            DP[0][i] = 1
        else:
            break

    for i in range(1,H):
        for j in range(1,W):
            DP[i][j] = (DP[i-1][j]+DP[i][j-1])%mod if grid[i][j] == '.' else 0

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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] = 1
for i in range(H):
    for j in range(W):
        if a[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] %= mod
print(dp[H-1][W-1])

Submission status: Accepted

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

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

dp = [[-1]*W+[0] for _ in range(H)] + [[0]*(W+1)]# dp[i][j] (i,j)からゴールまでの数をmodで割ったもの
dp[H-1][W-1] = 1

def rec(i,j):
  if dp[i][j] != -1:
    return dp[i][j]
  else:
    if A[i][j] == '#':
      return 0
    else:
      dp[i][j] = (rec(i+1, j) + rec(i, j+1)) % mod
      return dp[i][j]

print(rec(0,0))

Submission status: Accepted

Solution code:
r, c = map(int, input().split())
mask = 10**9 + 7
grid = []
for _ in range(r):
  grid.append(input())
dp = [[0 for _ in range(c)] for _ in range(r)]
dp[0][0] = 1
for i in range(1, r):
  dp[i][0] = dp[i-1][0] if grid[i][0] != '#' else 0
for j in range(1, c):
  dp[0][j] = dp[0][j-1] if grid[0][j] != '#' else 0

for i in range(1, r):
  for j in range(1, c):
    if grid[i][j] != '#':
      dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mask
print(dp[-1][-1] % mask)

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(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])%mod
        else:
            dp[i][j] = 0
            
        if i == 1 and j == 1:
            dp[i][j] = 1
            
print(dp[-1][-1])

Submission status: Accepted

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

Submission status: Accepted

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

"""
dp[y][x]: y行x列に到達する方法の数
"""
dp = [[0]*w for _ in range(h)]
dp[0][0] = 1
for y in range(h):
    for x in range(w):
        if y+1<h and maze[y+1][x] == ".":
            dp[y+1][x] = (dp[y+1][x] + dp[y][x]) % p
        if x+1<w and maze[y][x+1] == ".":
            dp[y][x+1] = (dp[y][x+1] + dp[y][x]) % p
print(dp[h-1][w-1])

Submission status: Accepted

Solution code:

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    mod = 1000000007

    H, W = map(int, input().split())
    a = [list(input().rstrip()) for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if a[i][j]=='#':
                a[i][j] = 0
    a[0][0] = 1
    for i in range(H):
        for j in range(W):
            if a[i][j]=='.':
                if i==0:
                    a[i][j] = a[i][j-1]
                elif j==0:
                    a[i][j] = a[i-1][j]
                else:
                    a[i][j] = a[i-1][j] + a[i][j-1]
    print(a[H-1][W-1]%mod)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    mod = 1000000007

    H, W = map(int, input().split())
    a = [list(input().rstrip()) for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if a[i][j]=='#':
                a[i][j] = 0
    a[0][0] = 1
    for i in range(H):
        for j in range(W):
            if a[i][j]=='.':
                if i==0:
                    a[i][j] = a[i][j-1]
                elif j==0:
                    a[i][j] = a[i-1][j]
                else:
                    a[i][j] = a[i-1][j] + a[i][j-1]
    print(a[H-1][W-1]%mod)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
mod=10**9+7
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
INF = 0
direc = [[1,0],[0,1]]
def dfs(start):
  Rt = [[INF]*W for _ in range(H)]
  Rt[start[0]][start[1]]=1
  q = deque([])# スタック
  q.append(start)
  while len(q)!=0:
    h,w = q.popleft()# スタック取りだし（はじめ）
    for d in direc:
      hs, ws = h + d[0], w + d[1]
      if not (0<=hs<H and 0<=ws<W):
        continue
      if Gd[hs][ws]=='.':
        if Rt[hs][ws]==INF:
          q.append([hs,ws])
        Rt[hs][ws] = (Rt[hs][ws] + Rt[h][w])%mod
  return Rt[H-1][W-1]
print(dfs([0,0]))

Submission status: Accepted

Solution code:
from collections import deque
mod=10**9+7
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
INF = 0
direc = [[1,0],[0,1]]
def dfs(start):
  Rt = [[INF]*W for _ in range(H)]
  Rt[start[0]][start[1]]=1
  q = deque([])# スタック
  q.append(start)
  while len(q)!=0:
    h,w = q.popleft()# スタック取りだし（はじめ）
    for d in direc:
      hs, ws = h + d[0], w + d[1]
      if not (0<=hs<H and 0<=ws<W):
        continue
      if Gd[hs][ws]=='.':
        if Rt[hs][ws]==INF:
          q.append([hs,ws])
        Rt[hs][ws] = (Rt[hs][ws] + Rt[h][w])%mod
  return Rt[H-1][W-1]
print(dfs([0,0]))

Submission status: Accepted

Solution code:
from collections import deque
mod=10**9+7
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
INF = 0
direc = [[1,0],[0,1]]
def dfs(start):
  Dis = [[INF]*W for _ in range(H)]
  Dis[start[0]][start[1]]=1
  q = deque([])# スタック
  q.append(start)
  while len(q)!=0:
    h,w = q.popleft()# スタック取りだし（先頭）
    for d in direc:
      hs, ws = h + d[0], w + d[1]
      if not (0<=hs<H and 0<=ws<W):
        continue
      if Gd[hs][ws]=='.':
        if Dis[hs][ws]==INF:
          q.append([hs,ws])
        Dis[hs][ws] = (Dis[hs][ws] + Dis[h][w])%mod
  return Dis[H-1][W-1]
print(dfs([0,0]))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(input())
dp = [[-1 for i in range(w)] for i in range(h)]
for i in range(w):
    if grid[0][i]!='#':
        dp[0][i] = 1
    else:
        break
for i in range(h):
    if grid[i][0]!='#':
        dp[i][0] = 1
    else:
        break
mod = 10**9+7
for i in range(1, h):
    for j in range(1, w):
        if grid[i][j] == '#':
            continue
        if dp[i][j-1] == -1 and dp[i-1][j] == -1:
            continue
        elif dp[i-1][j] == -1:
            dp[i][j] = dp[i][j-1]
        elif dp[i][j-1] == -1:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = (dp[i-1][j]+dp[i][j-1])%mod
print(max(dp[h-1][w-1], 0))

Submission status: Accepted

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

grid = []

for i in range(n):
  temp = list(input())
  grid.append(temp)
  
#dp[n][m]
mod = 10**9+7
dp = [[0 for i in range(m)] for j in range(n)]
dp[0][0] = 1

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

Submission status: Accepted

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

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


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

dp[0][0]=1
mod = 10**9 + 7
for i in range(n):
  for j in range(m):
    if grid[i][j]=='#':
      continue
    if i>0:
      dp[i][j] +=dp[i-1][j]%mod
    if j>0:
      dp[i][j] +=dp[i][j-1]%mod
      
print(dp[n-1][m-1]%mod)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
a=[]
mod=10**9+7

for i in range(H):
    temp=list(map(str,input()))
    a.append(temp)

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

for h in range(H):
    for w in range(W):
        if h==w==0:continue
        if a[h][w]=="#":continue
        if h-1<0:
            dp[h][w]=dp[h][w-1]%mod
        elif w-1<0:
            dp[h][w] = dp[h-1][w]%mod
        else:
            dp[h][w] = (dp[h][w -1] + dp[h -1][w])%mod

ans=dp[H-1][W-1]%mod
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
a=[list(input()) for i in range(H)]
#print(*a,sep='\n')
mod=10**9+7

dp=[[0]*W for i in range(H)]
dp[0][0]=1
for h in range(H):
    for w in range(W):
        if a[h][w]=='#':continue
        if h>=1:dp[h][w]+=dp[h-1][w]
        if w>=1:dp[h][w]+=dp[h][w-1]
#print(*dp,sep='\n')
print(dp[-1][-1]%mod)

Submission status: Accepted

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

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
MOD = 10 ** 9 + 7
count = [0]
dp = [[-1] * W for _ in range(H)]

def dfs(x, y):
  if x == W-1 and y == H-1:
    return 1
  ret = 0
  for nx, ny in ((1,0), (0,1)):
    nx += x
    ny += y
    if nx >= W or ny >= H:
      continue
    if dp[ny][nx] > -1:
      ret += dp[ny][nx]
    elif field[ny][nx] == ".":
      ret += dfs(nx, ny)
  dp[y][x] = ret % MOD
  return ret

dfs(0,0)
print(dp[0][0])

Submission status: Accepted

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

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
MOD = 10 ** 9 + 7
count = [0]
dp = [[-1] * W for _ in range(H)]

def dfs(x, y):
  ret = 0
  for nx, ny in ((1,0), (0,1)):
    nx += x
    ny += y
    if nx >= W or ny >= H:
      continue

    if nx == W-1 and ny == H-1:
      ret += 1
    elif dp[ny][nx] > -1:
      ret += dp[ny][nx]
    elif field[ny][nx] == ".":
      ret += dfs(nx, ny)
  dp[y][x] = ret % MOD
  return ret

dfs(0,0)
print(dp[0][0])

Submission status: Accepted

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

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
MOD = 10 ** 9 + 7
count = [0]
dp = [[-1] * W for _ in range(H)]

def dfs(x, y):
  ret = 0
  for nx, ny in ((1,0), (0,1)):
    nx += x
    ny += y
    if nx == W-1 and ny == H-1:
      ret += 1
      continue
    elif nx >= W or ny >= H:
      continue
    elif dp[ny][nx] > -1:
      ret += dp[ny][nx]
      continue
    elif field[ny][nx] == "#":
      continue
    else:
      ret += dfs(nx, ny)
  dp[y][x] = ret % MOD
  return ret

dfs(0,0)
print(dp[0][0])

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    readline=stdin.readline
    H,W=map(int,readline().split())
    grid=[0]*H
    for i in range(H):
        s=readline().strip()
        grid[i]=s
    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:
                if grid[i+1][j]==".":
                    dp[i+1][j]+=dp[i][j]
                    dp[i+1][j]%=mod
            if j+1<W:
                if grid[i][j+1]==".":
                    dp[i][j+1]+=dp[i][j]
                    dp[i][j+1]%=mod
    print(dp[H-1][W-1])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
c=["#"*(W+1)]+["#"+input()+"#" for _ in range(H)]+["#"*(W+1)]
mod=10**9+7

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

direction=[(0,-1),(0,1),(1,0),(-1,0)]
for h in range(1,H+1):
    for w in range(1,W+1):
        for x,y in direction:
            if c[h+x][w+y]==".":
                dp[h+x][w+y]=(dp[h+x][w+y]+dp[h][w])%mod

print(dp[H][W])

Submission status: Accepted

Solution code:
p = 10**9+7
h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

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

for i in range(1,h+1):
    for j in range(1,w+1):
        if maze[i-1][j-1] == '.':
            dp[i][j] += dp[i-1][j]%p + dp[i][j-1]%p


ans = dp[h][w]%p

print(ans)

Submission status: Accepted

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

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

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

dp[1][0] = 1

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

Submission status: Accepted

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

MOD = 10**9 + 7

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

# 一番上のマスは左から、一番左のマスは上からしか移動できない
for i in range(w):
    if filed[0][i] == '#':
        break
    dp[0][i] = 1
for i in range(h):
    if filed[i][0] == '#':
        break
    dp[i][0] = 1
    
# 残りのマスは、壁がなければ、左と上から移動できる
# dp[i][j] = dp[i-1][j] + dp[i][j-1]
for i in range(1, h):
    for j in range(1, w):
        if filed[i][j] == '#':
            continue
        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
l=[[0]*w]*h
m=[""]*h
for k in range(h):
  m[k]=input()
l[0][0]=1
for k in range(h):
  for j in range(w):
    if m[k][j]=="#":
      l[k][j]=0
    else:
      if k==0:
        if j!=0:
          l[k][j]=l[0][j-1]
      elif j==0:
        if k!=0:
          l[k][j]=l[k-1][j]
      else:
        l[k][j]=l[k-1][j]+l[k][j-1]
print(l[h-1][w-1]%1000000007)

Submission status: Accepted

Solution code:

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

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

mod = 10**9+7

a = []

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

lis[0][0] = 1
for i in range(H):

    for j in range(W):

        if a[i][j] == "#":
            continue

        if i > 0:
            lis[i][j] += lis[i-1][j]
        if j > 0:
            lis[i][j] += lis[i][j-1]

        lis[i][j] %= mod

print (lis[-1][-1])

Submission status: Accepted

Solution code:
H,W=map(int, input().split())
C=[[0]*W for i in range(H)]
D=[[] for i in range(H)]
p=10**9+7
for i in range(H):
    inp = input()
    for j in range(W):
        D[i].append(inp[j])
#print(D)
C[0][0]=1
for i in range(1,W):
    if(D[0][i]=="."):
        C[0][i]=C[0][i-1]
    else:
        C[0][i]=0

for i in range(1,H):
    if(D[i][0]=="."):
        C[i][0]=C[i-1][0]
    else:
        C[i][0]=0

for i in range(1,H):
    for j in range(1,W):
        if(D[i][j]=="#"):
            C[i][j]=0
        else:

            C[i][j]=C[i-1][j]+C[i][j-1]
            C[i][j]=C[i][j]%p
print(C[H-1][W-1])

Submission status: Accepted

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

def main():
    """dpをするときのてんぷれコ―ド"""
    #1:初期化
    mod = 10**9+7
    H, W = map(int, input().split())
    a = []
    for _ in range(H):
        a.append(input())
    dp = [[0]*(W) for _ in range(H)]

    #2:初期値
    dp[0][0] = 1
    
    #3:dp実行部(貰うDP)
    for i in range(H):
        for j in range(W):
            if a[i][j] == ".":             
                if i == 0 and j == 0:
                    continue
                elif i == 0 and a[i][j-1] == ".":
                    dp[i][j] += dp[i][j-1]
                elif j == 0 and a[i-1][j] == ".":
                    dp[i][j] += dp[i-1][j]
                else:
                    if a[i][j-1] == ".":
                        dp[i][j] += dp[i][j-1]
                    if a[i-1][j] == ".":
                        dp[i][j] += dp[i-1][j]

    #print(*dp,sep="\n")

    #4:出力
    print(dp[H-1][W-1] % mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

H, W = map(int, input().split())
A = [list(input()) for _ in range(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 i == j == 0:
            continue
        if A[i][j] == '.':
            dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j]) % MOD

print (dp[H][W])

# for tmp in dp:
#     print (tmp)

Submission status: Accepted

Solution code:

def main():
    H, W = map(int, input().split())

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

    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]

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


main()

Submission status: Accepted

Solution code:
mod = 10**9 + 7
H,W = map(int,input().split())
A = [list( input()) for i 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 and j == 0:
            dp[0][0] = 1
            continue
        if A[i][j] == ".":
            dp[i][j] = dp[i-1][j] + dp[i][j-1] 
print(dp[-1][-1]%mod)

Submission status: Accepted

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

dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
M = 10**9 + 7
for i in range(H):
  for j in range(W):
    if MAP[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] %= M
print(dp[-1][-1])

Submission status: Accepted

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

mod = 1000000007

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

for i in range(H):
  if A[i][0] == '#':
    break
  dp[i][0] = 1

for j in range(W):
  if A[0][j] == '#':
    break
  dp[0][j] = 1

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

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import copy

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

a = [["#" for _ in range(W + 2)]]
for i in range(H):
    p = deque(list(input()))
    p.appendleft("#")
    p.append("#")
    a.append(list(p))
a.append(["#" for _ in range(W + 2)])

dp = [[0 for _ in range(W + 10)] for _ in range(H + 10)]
dp[0][1] = 1
for i in range(1, H + 1):
    for l in range(1, W + 1):
        if a[i][l] != "#":
            dp[i][l] = (dp[i][l - 1] + dp[i - 1][l]) % MOD
print(dp[H][W] % MOD)

Submission status: Accepted

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

MOD = 1000000007  # type: int

def init(H, W, a):
    val=1
    for i in range(W):
        if a[0][i]=="#":
            val=0
            continue
        a[0][i]=val

    val=1
    for i in range(H):
        if a[i][0]=="#":
            val=0
            continue
        a[i][0]=val

def solve(H: int, W: int, a: "List[List[str]]"):
    init(H, W, a)
    for i in range(1,H):
        for j in range(1,W):
            if a[i][j]=="#": continue
            val=0
            if a[i-1][j]!="#": val+=a[i-1][j]
            if a[i][j-1]!="#": val+=a[i][j-1]
            a[i][j]=val%MOD
    print(a[H-1][W-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]]"
    a = [list(next(tokens)) for _ in range(H)]  # type: "List[List[str]]"
    solve(H, W, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for i in range(h):
    for j in range(w):
        if j+1 < w and rule[i][j+1] == '.':
            graph[i][j+1] = (graph[i][j+1] + graph[i][j]) % mod
        if i+1 < h and rule[i+1][j] == '.':
            graph[i+1][j] = (graph[i+1][j] + graph[i][j]) % mod

#print(graph)
print(graph[-1][-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

def main():
    h,w=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    dp=[[0]*w for _ in range(h)]
    for j in range(w):
        for i in range(h):
            if s[i][j]=='#':
                continue
            else:
                if j==0:
                    if i==0:
                        dp[i][j]=1
                    else:
                        dp[i][j]=dp[i-1][j]%(10**9+7)
                elif i==0:
                    dp[i][j]=dp[i][j-1]%(10**9+7)
                else:
                    dp[i][j]=(dp[i-1][j]+dp[i][j-1])%(10**9+7)
    print(dp[h-1][w-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

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][j]
            dp[i+1][j] %= 1000000007
        if j + 1 < w and a[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= 1000000007

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

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
Grid = [list(input()) for i in range(H)]
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 j+1 < W and Grid[i][j+1] == ".":
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= mod
        if i+1 < H and Grid[i+1][j] == ".":
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): #startline--------------------------------------------
    h,w = map(int,input().split())
    dp = [[0]*w for i in range(h)]
    a = [input() for i in range(h)]
    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][j]
                dp[i+1][j] %= Mod
            if j+1 < w and a[i][j+1] == ".":
                dp[i][j+1] += dp[i][j]
                dp[i][j+1] %= Mod

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

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

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

j = 1
for i in range(1, h+1):
    dp[i][j] = dp[i][j]%mod
    if i < h:
        if mt[i][0] == ".":
            dp[i + 1][1] = dp[i][1]
        else:
            dp[i + 1][1] = 0
    for j in range(1, w):
        if mt[i-1][j] == ".":
            dp[i][j+1] = dp[i][j] + dp[i-1][j+1]
        else:
            dp[i][j+1] = 0

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

Submission status: Accepted

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

for i in range(H):
    for j in range(W):
        if a[i][j] == ".":
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= mod
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= mod

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

Submission status: Accepted

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

dp[0][0] = 1

for i in range(h):
    for j in range(w):
        # 左に行けるとき
        if j + 1 < w and field[i][j+1] != "#":
            dp[i][j+1] += dp[i][j]
        # 下に行けるとき
        if i + 1 < h and field[i+1][j] != "#":
            dp[i+1][j] += dp[i][j]

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

Submission status: Accepted

Solution code:
r,c = [int(i) for i in input().split()]
mat = []
for i in range(r):
  arr = input()
  tmp = []
  for j in range(c):
    if arr[j] == '.':
      tmp.append(-1)
    else:
      tmp.append(-2)
  mat.append(tmp)

# assigning bottom row to 1 if val == -1 else 0
mat[r-1][c-1] = 1
for i in range(c-2, -1, -1):
  if mat[r-1][i] == -1:
    mat[r-1][i] = mat[r-1][i+1]
  elif mat[r-1][i] == -2:
    mat[r-1][i] = 0

#assiginign to rightmost complex
for j in range(r-2, -1, -1):
  if mat[j][c-1] == -1:
    mat[j][c-1] = mat[j+1][c-1]
  elif mat[j][c-1] == -2:
    mat[j][c-1] = 0

# compute for represent
for i in range(r-2, -1, -1):
  for j in range(c-2, -1, -1):
    if mat[i][j] == -2:
      mat[i][j] = 0
    else:
      mat[i][j] = (mat[i+1][j] + mat[i][j+1])%1000000007
print("%s" % mat[0][0])

Submission status: Accepted

Solution code:
H, W = [int(item) for item in input().split()]
grid = [[item for item in input().strip()] for _ in range(H)]

# print(H, W) 
# print(grid)

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

for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            pass
        else:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j])%(10**9+7)

print(dp[H][W])