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())
dp = [[0] * W for i in range(H)]
MOD = 10 ** 9 + 7
T = [[] for i in range(H)]
for i in range(H):
    T[i] = list(input())

for j in range(W):
    if T[0][j] == '.':
        dp[0][j] = 1
    else:
        break
for i in range(H):
    if T[i][0] == '.':
        dp[i][0] = 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]
        dp[i][j] %= MOD
        if T[i][j] == '#':
            dp[i][j] = 0

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from sys import stdin
def input(): return sys.stdin.readline().strip()

modn = 10 ** 9 + 7
H , W = map(int, input().split())
ahw = [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 ahw[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] = dp[i][j] % modn
print(dp[-1][-1])

Submission status: Accepted

Solution code:
ROUTE, WALL = 0, 1
def main():
    H, W = [int(n) for n in input().split()]
    H, W = H+1, W+1
    grid = [[ROUTE]*W for i in range(H)]
    for h in range(H):
        if h == 0:
            grid[0] = [WALL] * W
            continue
        instr = "#" + input()
        for w, c in enumerate(instr):
            grid[h][w] = ROUTE if c == "." else WALL
    dp = [-1]*(H*W)
    dp[coord_to_num(W, 1,1)]=1
    for crd in range(H*W):
        if dp[crd] != -1:
            continue
        h, w = num_to_coord(W, crd)
        if grid[h][w] == WALL:
            dp[crd] = 0
            continue
        up = dp[coord_to_num(W,h-1, w)]
        down = dp[coord_to_num(W, h, w-1)]
        dp[coord_to_num(W, h, w)] = up+down
    print(dp[coord_to_num(W, H-1, W-1)] % (10 ** 9 + 7))


def num_to_coord(W, num):
    return (num//W, num%W)
def coord_to_num(W, h, w):
    return h * W + w

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

h, w = map(int, input().split())
a = [['#'] * (w+2)] + [['#'] + list(input()) + ['#'] for _ in range(h)] + [['#'] * (w+2)]

MOD = 10 ** 9 + 7

#for x in a: print(x)

dp = [[0 for _ in range(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 a[i-1][j] == '#' and a[i][j-1] == '#':
            continue
        elif a[i-1][j] == '#':
            dp[i][j] = dp[i][j-1]
        elif a[i][j-1] == '#':
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD

print(dp[h][w])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

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

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

for i in range(H):
    for j in range(W):
        if grid[i][j] != '.':
            continue
        if i == 0 and j == 0:
            dp[i][j] = 1
        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][j - 1] + dp[i - 1][j]) % MOD

print(dp[i][j])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
mod=10**9+7
h,w=map(int,input().split())
wall='#'*(w+2)
MAP=[wall]
for _ in range(h):
    MAP.append('#'+input().strip()+'#')
MAP.append(wall)
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 MAP[i][j]=='.':
            DP[i][j]+=DP[i-1][j]+DP[i][j-1]
            DP[i][j]%=mod
print(DP[h][w])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    """
    N個の足場があります。足場には1,2,…,Nと番号が振られています。 
    各i (1≤i≤N) について、足場 i の高さは hi です。
    最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。
    足場 i にいるとき、足場 i+1 または i+2 へジャンプする。
    このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。
    カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

    制約
        入力はすべて整数である。
    2≤N≤10**5
    1≤hi≤10**4
    """
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return

#B
def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return

#C
def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return

#D
def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return

#E
def E():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**9
    1≤wi≤W
    1≤vi≤10**3"""
    n, w = LI()
    wv = LIR(n)
    dp = [[float("INF") for i in range(10 ** 5 + 1)] for k in range(n + 1)]
    dp[0][0] = 0
    for i in range(n):
        for k in range(10 ** 5 + 1):
            if k < wv[i][1]:
                dp[i + 1][k] = dp[i][k]
            else:
                dp[i + 1][k] = min(dp[i][k], dp[i][k - wv[i][1]] + wv[i][0])
    ans = 0
    for i in range(10 ** 5 + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

    return

#F
def F():
    s = "abc"*1000
    t = "abc"*1000
    dp = [[0 for i in range(len(t)+1)] for k in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                if dp[i][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]
        
    print(dp[len(s)][len(t)])
    return

#G
def G():
    n, m = LI()
    xy = LIR_(m)
    edge = [[] for i in range(n)]
    for x,y in xy:
        edge[x].append(y)
    dp = [0 for i in range(n)]
    def ans(dp, i):
        #print(dp, i)
        if dp[i] != 0:
            return dp[i]
        else:
            if len(edge[i]) == 0:
                return 0
            ansb = 0
            for k in edge[i]:
                #print(dp, k , i)
                ansb = max(ansb, ans(dp, k) + 1)
                dp[i] = max(ansb, dp[i])
                #print(dp)
            return ansb
            
    for i in range(n):
        dp[i] = ans(dp, i)
    print(max(dp))
    return

#H
def H():
    h, w = LI()
    a = SR(h)
    dp = [[0 for i in range(w)] for k in range(h)]
    for i in range(w):
        if a[0][i] == "#":
            break
        dp[0][i] = 1
    for i in range(h):
        if a[i][0] == "#":
            break
        dp[i][0] = 1
    for i in range(1,w):
        for k in range(1, h):
            #print(i,k, dp)
            if a[k - 1][i] == ".":
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k - 1][i] + dp[k][i - 1] % mod
                else:
                    dp[k][i] = dp[k - 1][i]
            else:
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k][i - 1]
    print(dp[h-1][w-1] % mod)

    return

#I
def I():
    return 
#J

#K


#L

#M
#N
# O
# P
# Q
# R
# S
# T
# U
# V
# W
# X
# Y
# Z


#Solve
if __name__ == '__main__':
    H()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])
#B
def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])

#C
def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))

#D
def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))
#E
def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("inf") for i in range(V+1)] for j in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(V+1)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()

#F
def F():
    s = S()
    t = S()
    dp = [[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

    i = len(s)
    j = len(t)
    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:
            i -= 1
            j -= 1
            ans = s[i]+ans
    print(ans)
#G
def G():
    n,m = LI()
    e = LIR(m)
    dp = [0 for j in range(m+1)]
    for i in range(m):
        x,y = e[i]
        dp[i+1][y] = max(dp[i][y],dp[i][x]+1)
    ans = 0
    for i in range(m+1):
        ans = max(dp[i])
    print(ans)
#H
def H():
    h,w = LI()
    s = SR(h)
    dp = [[0 for i in range(w)] for j in range(h)]
    dp[0][0] = 1
    for i in range(h-1):
        for j in range(w-1):
            if s[i+1][j] == ".":
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= mod
            if s[i][j+1] == ".":
                dp[i][j+1] += dp[i][j]
                dp[i][j+1] %= mod
    for j in range(w-1):
        if s[h-1][j+1] == ".":
            dp[h-1][j+1] += dp[h-1][j]
            dp[h-1][j+1] %= mod
    for i in range(h-1):
        if s[i+1][w-1] == ".":
            dp[i+1][w-1] += dp[i][w-1]
            dp[i+1][w-1] %= mod
    print(dp[h-1][w-1])
#Solve
if __name__ == "__main__":
    H()

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


H,W = map(int, input().split())
An = [""] * H
for i in range(H):
  An[i] = str(input())

# dp[i][j] := (1,1)->(i,j)への経路数
dp = [[0 for j in range(W+1)] for i in range(H+1)]
dp[1][1] = 1
for i in range(1,H+1):
  for j in range(1,W+1):
    if An[i-1][j-1] == '.':
      dp[i][j] = (dp[i][j]+dp[i-1][j]+dp[i][j-1]) % (10**9+7)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7

def f(h, w, grid):
    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 grid[i][j] == ".":
                dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
                if dp[i][j] > mod:
                    dp[i][j] -= mod
    return(dp[h][w])

h, w = map(int, input().split()) # 2 <= h, w <= 10000
grid = [["#"] + list(input().rstrip()) for _ in range(h)]
grid = [["#"] * (w + 1)] + grid
print(f(h, w, grid))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
dp=[0]*(n)
for i in range(n):
	s=input()
	dp[i]=[-1]*m
	for j in range(m):
		if s[j]=="#":
			dp[i][j]=0
fill=1
for i in range(m):
	if dp[0][i]<0:
		dp[0][i]=fill
	else:
		fill=0
fill=1
for i in range(1,n):
	if dp[i][0]<0:
		dp[i][0]=fill
	else:
		fill=0
for i in range(1,n):
	for j in range(1,m):
		if dp[i][j]<0:
			dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007
print(dp[n-1][m-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W = list(map(int, input().split()))
L = []
ansL = [[0 for i in range(W)] for j in range(H)]
ansL[0][0] = 1

for i in range(H):
	L.append(list(input()))

for i in range(W):
	for j in range(H):
		if L[j][i] == ".":
			if i >= 1:
				ansL[j][i] += ansL[j][i - 1]
			if j >= 1:
				ansL[j][i] += ansL[j - 1][i]
			ansL[j][i] = ansL[j][i] % 1000000007

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

Submission status: Accepted

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

Submission status: Accepted

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

md = 1e9 + 7
dp = [ [0]*W for _ in range(H) ]
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        if a[h][w] == '.':
            if w > 0:
                dp[h][w] += dp[h][w-1]
            if h > 0:
                dp[h][w] += dp[h-1][w]
        dp[h][w] %= md

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

Submission status: Accepted

Solution code:
H, W = (int(i) for i in input().split()) 

G = []
for i in range(H):
    G.append(input())

# dp[i][j] : i, j までの経路 
min = 0
dp = [[min for i in range(W + 1)] for j in range(H + 1)]
dp[1][1] = 1

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


for hh in range(H):
    for ww in range(W):
        if G[hh][ww] == "#":
            dp[hh + 1][ww + 1] = 0
        else:
            if hh == 0 and ww == 0:
                dp[0][0] = 1
            else:
                dp[hh + 1][ww + 1] = dp[hh][ww + 1] + dp[hh+1][ww]


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/7
Update on 2019/3/
Solved on 2019/3/  
@author: shinjisu
"""


# Educational Dynamic Programming
# import math
#import numpy as np
#import sys
#sys.setrecursionlimit(10**6)


def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]
# def getIntList(): return np.array(input().split(), dtype=np.longlong)


def zeros(n): return [0]*n
# def zeros(n): return np.zeros(n, dtype=np.longlong)


def getIntLines(n): return [int(input()) for i in range(n)]
def getIntLines(n):
    data = zeros(n)
    for i in range(n):
        data[i] = getInt()
    return data


def getIntMat(n, m):  # n行に渡って、1行にm個の整数
    mat = zeros((n, m))
    #dmp(mat)
    for i in range(n):
        mat[i] = getIntList()
    return mat


def zeros2(n, m): return [zeros(m) for i in range(n)] # obsoleted zeros((n, m))で代替

ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def prob_H_v1():  # Grid 1    AC 10  TLE 6
    H, W = getIntList()
    dmp((H, W), 'H, W')
    a = []
    for i in range(H):
        a.append(input())
    dmp(a)
    WALL = '#'
    BLANK = '.'
    dp = zeros((H+1, W+1))
    dp[1, 1] = 1
    dmp(dp, 'dp initial')
    for i in range(H):
        for j in range(W):
            if a[i][j] == BLANK and (i > 0 or j > 0):
                dp[i+1, j+1] = (dp[i, j+1] + dp[i+1, j]) % N1097

    dmp(dp, 'dp')
    return dp[H, W]


def prob_H_v2():  # Grid 1  AC 11  TLE 5
    H, W = getIntList()
    dmp((H, W), 'H, W')
    a = []
    for i in range(H):
        a.append(input())
    dmp(a)
    WALL = '#'
    BLANK = '.'
    dp = zeros((H+1, W+1))
    dp[1, 1] = 1
    dmp(dp, 'dp initial')
    for i in range(1, H):
        if a[i][0] == BLANK:
            dp[i+1, 1] = dp[i, 1]
    for j in range(1, W):
        if a[0][j] == BLANK:
            dp[1, j+1] = dp[1, j]
    for i in range(1, H):
        for j in range(1, W):
            if a[i][j] == BLANK:
                dp[i+1, j+1] = (dp[i, j+1] + dp[i+1, j]) % N1097

    dmp(dp, 'dp')
    return dp[H, W]




def prob_H():  # Grid 1    AC 11  TLE 5
    H, W = getIntList()
    dmp((H, W), 'H, W')
    a = []
    for i in range(H):
        a.append(input())
    dmp(a)
    WALL = '#'
    BLANK = '.'
    dp = zeros2(H+1, W+1)
    dp[0][1] = 1  # [1,1]ではないことがポイント
    dmp(dp, 'dp initial')
    for i in range(H):
        for j in range(W):
            if a[i][j] == WALL:
                continue
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][ j]) % N1097

    dmp(dp, 'dp')
    return dp[H][ W]


debug = False  # True False
ans = prob_H()
print(ans)
#for row in ans:
#    print(row)

Submission status: Accepted

Solution code:

def count_paths(A, DP, N, M):
    DP[0][0] = 1
    for i in range(N):
        for j in range(M):
            if i==0 and j==0:
                DP[0][0] = 1
            else:
                if A[i][j] == '#':
                    DP[i][j] = 0
                else:
                    DP[i][j] = (DP[i-1][j]+DP[i][j-1])%(1000000007)
    return DP[N-1][M-1]
N, M = [int(s) for s in input().split(" ")]
A = []
DP = []
for i in range(N):
    DP.append([0]*M)
    z = [ch for ch in input()]
    A.append(z)
result = count_paths(A, DP, N, M)
print("{}".format(result))

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
"""
This file is part of https://github.com/cheran-senthil/PyRival
Copyright 2019 Cheran Senthilkumar <hello@cheran.io>

"""
from __future__ import division, print_function

import itertools
import math
import os
import sys
from atexit import register
from io import BytesIO


class dict(dict):
    """dict() -> new empty dictionary"""

    def items(self):
        """D.items() -> a set-like object providing a view on D's items"""
        return dict.iteritems(self)

    def keys(self):
        """D.keys() -> a set-like object providing a view on D's keys"""
        return dict.iterkeys(self)

    def values(self):
        """D.values() -> an object providing a view on D's values"""
        return dict.itervalues(self)


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


range = xrange

filter = itertools.ifilter
map = itertools.imap
zip = itertools.izip

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

FMOD = 1000000007.0
fmod = lambda x: x - FMOD * math.trunc(x / FMOD)

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

grid = [input() + '#' for _ in range(h)]
grid.append('#' * (w + 1))

dp = [[0.0] * (w + 1) for _ in range(h + 1)]
dp[-2][-2] = 1.0

for i in range(h - 1, -1, -1):
    for j in range(w - 1, -1, -1):
        if (i == h - 1) and (j == w - 1):
            continue
        dp[i][j] = fmod((dp[i + 1][j] if grid[i + 1][j] == '.' else 0.0) +
                        (dp[i][j + 1] if grid[i][j + 1] == '.' else 0.0))

print(int(dp[0][0]) % 1000000007)

Submission status: Accepted

Solution code:
H, W = [int(i) for i in input().split()]
A = [[s for s in input()] for j in range(H)]
p = 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 h + 1 < H and A[h+1][w] == '.':
            DP[h+1][w] += DP[h][w]
            DP[h+1][w] %= p
        if w + 1 < W and A[h][w+1] == '.':
            DP[h][w+1] += DP[h][w]
            DP[h][w+1] %= p

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
map = [[] * m for _ in range(n)]
dp = [[0] * (m+1) for _ in range(n + 1)]

for _ in range(n):
    tmp = input()
    for __ in tmp:
        map[_].append(__)

if map[n-1][m-1] == '#':
    print(0)

for t1 in range(n)[::-1]:
    if map[t1][m-1] != '#':
        dp[t1 + 1][m] = 1
    else:
        break

for t1 in range(m)[::-1]:
    if map[n-1][t1] != '#':
        dp[n][t1 + 1] = 1
    else:
        break

for i in range(1,n+1)[::-1]:
    for j in range(1,m + 1)[::-1]:
        if map[i-1][j-2] != '#' and map[i-2][j-1] != '#':
            dp[i-1][j-1] = dp[i][j-1] + dp[i-1][j]
        elif map[i -1][j-2] == '#' and map[i -2][j-1] != '#':
             dp[i-1][j-1] = dp[i-1][j]
        elif  map[i -1][j-2] != '#' and map[i -2][j-1] == '#':
             dp[i-1][j-1] = dp[i][j-1]
        else:
            dp[i-1][j-1] = 0

print(dp[1][1] % 1000000007)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

INF = 10 ** 5
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


h, w = LI()
B = [SI() for _ in range(h)]

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

for i in range(h):
    for j in range(w):
        if B[i][j] == '#':
            continue
        dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j]) % MOD

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[list(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 i+1<h and s[i+1][j]=='.':dp[i+1][j]+=dp[i][j]
        if j+1<w and s[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())
a=[input() for _ in range(h)]

dp = [[0]*w for _ in range(h)]
dp[0][0]=1
for i in range(w):
    if a[0][i] == "#":
        break
    dp[0][i] = 1
for j in range(h):
    if a[j][0] == "#":
        break
    dp[j][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]
print(dp[h-1][w-1]%(10**9+7))

Submission status: Accepted

Solution code:
def main(): 
  H, W = list(map(int, input().split()))
  a = []
  for i in range(H):
    a.append(list(input()))
    
  DP = [[0 for i in range(W)] for j in range(H)]
  
  DP[0][0] = 1
  for i in range(1, W):
    if a[0][i] == ".":
      DP[0][i] = 1
    else:
      break
  for i in range(1, H):
    if a[i][0] == ".":
      DP[i][0] = DP[i - 1][0]
    for j in range(1, W):
      if a[i][j] == ".":
        DP[i][j] = int((DP[i - 1][j] + DP[i][j - 1]) % (1e9 + 7))
  print(DP[-1][-1]) 
main()

Submission status: Accepted

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

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

dp[0][0] = 1

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

for j in range(1, w):
    if A[0][j] == '.':
        dp[0][j] = dp[0][j - 1]

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

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

Submission status: Accepted

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

mod = 10**9 + 7

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

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

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = [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 < H-1 and A[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
        if j < W-1 and A[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= MOD
print(dp[-1][-1])