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(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]

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

Submission status: Accepted

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

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

def main():
    dp[0][1] = 1

    for i in range(H):
        for j in range(W):
            if grid[i][j] != '#':
                dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j]) % max_num
            

    # print(dp)
    print(dp[H][W])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
M = [input() for _ in range(H)]
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 M[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:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**9 + 7

def main():
  h, w = map(int, input().strip().split())
  dp = [[0]*(w+1) for _ in range(h+1)]
  maze = [input().strip() for _ in range(h)]
  dp[1][0] = 1
  for i in range(1, h+1):
    for j in range(1, w+1):
      if maze[i-1][j-1] == '#':
        continue
      dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MAX
  print(dp[-1][-1])


if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  import sys
  import numpy as np
  input=sys.stdin.readline
  h,w=map(int,input().split())
  meize=[list(input()) for i in range(h)]
  mod=10**9+7

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

  dp[0][1]=1
  for i in range(h):
    for j in range(w):
      if meize[i][j]=='#':
        dp[i+1][j+1]=0
      else:
        dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]
        dp[i+1][j+1]%=mod

  print(dp[h][w]%mod)
  
if __name__=='__main__':
  main()

Submission status: Accepted

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

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

dp[0][1]=1
for i in range(h):
  for j in range(w):
    if meize[i][j]=='#':
      dp[i+1][j+1]=0
    else:
      dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]
      dp[i+1][j+1]%=mod

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

Submission status: Accepted

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

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

dp[0][0] = 1

for i in range(h):
  for j in range(w):
    if a[i][j] == "#":
      continue
    else:
      if i > 0:
        dp[i][j] += dp[i-1][j]
        dp[i][j] %= inf
      if j > 0:
        dp[i][j] += dp[i][j-1]
        dp[i][j] %= inf

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

Submission status: Accepted

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

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

dp[0][0] = 1

for i in range(h):
  for j in range(w):
    if a[i][j] == "#":
      continue
    else:
      if i > 0:
        dp[i][j] += dp[i-1][j]
        dp[i][j] %= inf
      if j > 0:
        dp[i][j] += dp[i][j-1]
        dp[i][j] %= inf

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

Submission status: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.readline

    mod = 10 ** 9 + 7

    h, w = map(int, readline().split())
    a = [readline().rstrip() for _ in range(h)]

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

    for r in range(h):
        for c in range(w):
            if a[r][c] == '#': continue
            if r > 0:
                dp[r][c] += dp[r - 1][c]
            if c > 0:
                dp[r][c] += dp[r][c - 1]
            dp[r][c] %= mod

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

matrix = [[1]*W for i in range(H)]

# print(matrix)
for i in range(H):
    for j in range(W):
        if gridlist[i][j] == '#':
            matrix[i][j] = 0

# print(matrix)

for i in range(H):
    for j in range(W):
        up = 0
        left = 0
        if matrix[i][j] == 0:
            continue
        if i==0 and j == 0:
            continue
        if i > 0:
            left = matrix[i-1][j]
        if j > 0:
            up = matrix[i][j-1]
        matrix[i][j] = left + up
        # print(matrix)

print(matrix[i][j] % (10**9 + 7))

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
grid = [list(input()) for i in range(H)]
#print(grid)
#dp =[[1] if grid[i][j] == '.' else [0] for j in range(W) for i in range(H)]
dp = []
for i in range(H):
    retsu = []
    for j in range(W):
        if grid[i][j] == '.':
            retsu.append(1)
        else:
            retsu.append(0)
    dp.append(retsu)
#print(dp)
for i in range(H):
    for j in range(W):
        if j - 1 >= 0 and i-1>=0:
            if grid[i][j] == '#':
                continue
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
        elif i - 1 >= 0:
            if grid[i][j] == '#':
                continue
            dp[i][j] = 0 + dp[i-1][j]
        elif j - 1 >= 0:
            if grid[i][j] == '#':
                continue
            dp[i][j] = dp[i][j-1] + 0
        else:
            dp[i][j] = 1

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

Submission status: Accepted

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

maze = [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 maze[i][j] != '#':
            if i != 0:
                dp[i][j] = (dp[i][j] + dp[i-1][j] % d) % d
            if j != 0:
                dp[i][j] = (dp[i][j] + dp[i][j-1] % d) % d

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

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  dp=[[0]*w for _ in range(h)]
  dp[0][0]=1

  l=[S() for _ in range(h)]

  for i in range(h):
    for j in range(w):
      
      y=i-1
      x=j-1

      if y<0 and x<0:
        continue
      if l[i][j]=='#':
        continue
      if y<0:
        dp[i][j]=dp[i][j-1]
      elif x<0:
        dp[i][j]=dp[i-1][j]
      else:
        dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod

  return dp[h-1][w-1]

# main()
print(main())

Submission status: Accepted

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

Submission status: Accepted

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

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==j==0:
   continue
  if l[i][j]=='#':
   dp[i][j]==0
   continue

  if i-1>=0 and l[i-1][j]=='.':
   dp[i][j]+=dp[i-1][j]
  if j-1>=0 and l[i][j-1]=='.':
   dp[i][j]+=dp[i][j-1]

  dp[i][j]%=mod

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

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
temp=[]
mod=(10**9)+7
for r in range(H):
    s=input()
    temp.append(s)
grid=[]
for i in temp:
    x=[]
    for j in i:
        if j==".":
            x.append(0)
        else:
            x.append(1)
    grid.append(x)
dp=[]
for i in range(H):
    x=[-1]*W
    for j in range(W):
        if grid[i][j]==1:
            x[j]=0
    dp.append(x)
dp[H-1][W-1]=1
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if grid[i][j]==1 or (i==H-1 and j==W-1):
            continue
        else:
            a=0
            b=0
            if (j+1)<W:
                a=dp[i][j+1]
            if (i+1)<H:
                b=dp[i+1][j]
            dp[i][j]=a+b
print(dp[0][0]%mod)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    a=[[] for _ in range(H+2)]
    a[0]=a[H+1]='#'*(W+2)
    for i in range(1,H+1):
        a[i]='#'+input()+'#'
    dp=[[0]*(W+2) for _ in range(H+2)]
    for column in range(1,H+1):
        for row in range(1,W+1):
            if column==row==1:
                dp[column][row]=1
            elif a[column][row]=='.':
                dp[column][row]=(dp[column-1][row]+dp[column][row-1])%MOD
    print(dp[H][W])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    a=[[] for _ in range(H+2)]
    a[0]=a[H+1]='#'*(W+2)
    for i in range(1,H+1):
        a[i]='#'+input()+'#'
    dp=[[0]*(W+2) for _ in range(H+2)]
    dp[1][1]=1
    que=deque()
    que.append((1,1))
    dx=[1,0]
    dy=[0,1]
    used=[[False]*(W*2) for _ in range(H+2)]
    used[1][1]=True
    while que:
        y,x=que.popleft()
        for k in range(2):
            ny,nx=y+dy[k],x+dx[k]
            if a[ny][nx]=='.':
                dp[ny][nx]+=dp[y][x]
                dp[ny][nx]%=MOD
                if not used[ny][nx]:
                    que.append((ny,nx))
                    used[ny][nx]=True
    print(dp[H][W])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

#迷路の初期化
a = [[-1] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    s = input()
    for j in range(1,W+1):
        if s[j-1] == ".":
            a[i][j] = 0
        elif s[j-1] == "#":
            a[i][j] = -1
        else:
            print("ERROR")

#dpの初期化
dp_sum = [[0] * (W+2) for i in range(H+2)]
#step
steplst =  [[] for i in range((H+W)+2)]
#stepdxy = [[1,0],[-1,0],[0,1],[0,-1]]
stepdxy = [[1,0],[0,1]]

def do_step(n):
    stepok = 0
    if n == 1:
        x,y = 1,1
        a[x][y] = -9
        for dx,dy in stepdxy:
            if a[x+dx][y+dy] == 0 or a[x+dx][y+dy] == n:
                dp_sum[x+dx][y+dy] += 1
                a[x+dx][y+dy] = n
                steplst[n].append([x+dx,y+dy])
                stepok = 1
    else:
        for x,y in steplst[n-1]:
            for dx,dy in stepdxy:
                if a[x+dx][y+dy] == 0:
                    dp_sum[x+dx][y+dy] += dp_sum[x][y]
                    a[x+dx][y+dy] = n
                    steplst[n].append([x+dx,y+dy])
                    stepok = 1
                elif a[x+dx][y+dy] == n:
                    dp_sum[x+dx][y+dy] += dp_sum[x][y]
    return stepok

stepn = 1
while do_step(stepn) == 1:
    #for i in range(len(dp_sum)):
    #    print(dp_sum[i],a[i])
    stepn += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 10 ** 9 + 7
dp = [[0 for j in range(w + 1)] for i 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]) % MOD
            dp[i + 1][j + 1] %= MOD
print(dp[-1][-1])

Submission status: Accepted

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

al = []

MOD = 10**9 + 7
for _ in range(h):
   a = list(input())
   al.append(a)

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

for i in range(h):
    for j in range(w):
        if i+1 < h and al[i+1][j] == ".":
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
        if j+1 < w and al[i][j+1] == ".":
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= MOD
            
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # LCS
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    # http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
    # トポロジカルソート
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)
#    print(Order)
    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

def examH():
    H, W = LI()
    A = [SI() 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
            dp[i][j] %=mod
            if i+1<H and dp[i+1][j]!="#":
                dp[i+1][j] +=dp[i][j]
            if j+1<W and dp[i][j+1]!="#":
                dp[i][j+1] +=dp[i][j]
    ans = dp[-1][-1]
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examH()

"""

"""

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
Grid = [list(input()) for _ in range(H)]
lis = [[0]*W for _ in range(H)]
lis[0][0] = 1
M = 10**9+7

for i in range(H):
    for j in range(W):
        if i != H-1 and Grid[i+1][j] == ".":
            lis[i+1][j] += lis[i][j]%M
        if j != W-1 and Grid[i][j+1] == ".":
            lis[i][j+1] += lis[i][j]%M

print(lis[H-1][W-1] % M)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
mod=10**9+7
W0=[list('#'*(w+2))]
Wh=[list('#'*(w+2))]
HW=W0+[list('#'+input()+'#') for i in range(h)]+Wh
# dp[i][j]をi,jまでの組み合わせ
dp=[[0]*(w+1) for i in range(h+1)]
for i in range(1,h+1):
    for j in range(1,w+1):
        if i==1 and j==1:
            dp[i][j]=1
        else:
            if HW[i][j]=='.':
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
            else:
                dp[i][j]=0
print(dp[h][w])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

h,w = mii()
mat = llstr(h)
dp = [[0]*w for i in range(h)]
dp[0][0]=1

for i in range(h):
    for j in range(w):
        if i==0 and j==0:
            continue
        if i==0 and mat[i][j]==".":
            dp[i][j] = dp[i][j-1]
        elif i>0 and mat[i][j]==".":
            if mat[i-1][j]=="#":
                dp[i][j] = dp[i][j-1]
            else:
                dp[i][j] =dp[i][j-1]+dp[i-1][j]
    
print(dp[-1][-1]%(mod))

Submission status: Accepted

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

MOD = 10 ** 9 + 7

#dp[h][w]
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 A[i+1][j] == "."):
      dp[i+1][j] += dp[i][j] 
    if (j + 1 < w and A[i][j+1] == "."):
      dp[i][j+1] += dp[i][j] 
ans = dp[h-1][w-1] % MOD
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
M = [list(input()) for i in range(H)]
p = 10**9 + 7

M[0][0] = 1
for h in range(H):
  for w in range(W):
    if M[h][w] == ".":
      M[h][w] = ((M[h-1][w] if h-1 >= 0 and M[h-1][w] != "#" else 0) + (M[h][w-1] if w-1 >= 0 and M[h][w-1] != "#" else 0)) % p
print(M[-1][-1])

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
H, W = map(int, input().split())
grid = np.zeros((H + 2, W + 2), dtype=int)
for i in range(H):
    grid[i+1][1:-1] = [1 if j == "." else 0 for j in input()]
grid = grid.tolist()

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

cost[1][1] = 1
for i in range(1, H + 1):
    for j in range(1, W + 1):
        c = cost[i][j]
        if grid[i+1][j]:
            cost[i+1][j] += c
            cost[i+1][j] %= mod
        if grid[i][j+1]:
            cost[i][j+1] += c
            cost[i][j+1] %= mod

ans = cost[H][W]
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
h,w = map(int,input().split())
grid = [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 grid[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[-1][-1] % MOD)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
a=[]
a.append("."*(W+2))

for _ in range(H):
    a.append("."+input()+".")
a.append("."*(W+2))
    
mod=10**9+7

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 a[i][j]==".":
            add=0
            if a[i-1][j]==".":
                add+=dp[i-1][j]
            if a[i][j-1]==".":
                add+=dp[i][j-1]
            dp[i][j]+=add
            dp[i][j]%=mod
            
print(dp[H][W]%mod)

Submission status: Accepted

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

def no_of_paths(i, j, arr, dp):

  if dp[i][j] is not None:
    return dp[i][j]

  if arr[i][j] == '#':
    return 0

  if i == 0 and j == 0:
    return dp[i][j]

  count = 0

  if i-1 >= 0:
    count  += no_of_paths(i-1, j, arr, dp) % (10**9 + 7)
  if j-1 >= 0:
    count += no_of_paths(i, j-1, arr, dp) % (10**9 + 7)

  dp[i][j] = count % (10**9 + 7)
  return dp[i][j]

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

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

dp = [[None]*W for _ in range(H)]
dp[0][0] = 1
print(no_of_paths(H-1, W-1, data, dp))

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] == '.':
            if i + 1 < h:
                if a[i+1][j] == '.':
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= mod
            if j + 1 < w:
                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:
from collections import deque
h, w = list(map(int, input().split()))
grid = []
for i in range(h):
    grid.append(list(input()))
#x,y渡すと、（h,w）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
ans = [[0 for i in range(w)] for j in range(h)]
#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
ans[0][0] = 1
mod = 10**9+7
for i in range(h):
    for j in range(w):
        if grid[i][j] != '#':
            if i - 1 >= 0:
                ans[i][j] += ans[i-1][j]
            if j - 1 >= 0:
                ans[i][j] += ans[i][j-1]
        else:
            ans[i][j] = 0
        ans[i][j] %= mod
print(ans[-1][-1])

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

H,W = imn()
a = [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+1 < H and a[i+1][j] == '.': dp[i+1][j] = m_add(dp[i+1][j], dp[i][j])
        if j+1 < W and a[i][j+1] == '.': dp[i][j+1] = m_add(dp[i][j+1], dp[i][j])
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
MOD = 10**9+7
def add_mod(a,b): return (a+b) % MOD

H,W = imn()
aw = [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+1 < H and aw[i+1][j] == '.': dp[i+1][j] = add_mod(dp[i+1][j], dp[i][j]) 
        if j+1 < W and aw[i][j+1] == '.': dp[i][j+1] = add_mod(dp[i][j+1], dp[i][j])
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
MOD = 10**9+7

H,W = imn()
aw = [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 aw[i+1][j] == '.': dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD 
        if j+1 < W and aw[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:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
MOD = 10**9+7

H,W = imn()
a = [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+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])