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:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
"""inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; cnt = 0; ansli = []; tmpli = []; candili = []; stillset = set()
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]"""
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def s_list(): return list(input())
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]#NumberGrid
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def grid(n): return [s_list() for _ in range(n)]

def main():
    mod = 10 ** 9 + 7
    h, w = wi()
    a = grid(h)
    dp = [[0 for _ in range(w + 1)] for _ in range(h + 1)]
    dp[1][1] = 1
    # (H,W)へ行く場合の数は、(H−1,W),(H,W−1)へ行く場合の数の和
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if not (i == 1 and j == 1):
                if a[i - 1][j - 1] == '#':
                    dp[i][j] = 0
                else:
                    dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
    ans = dp[h][w]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_h

h, w = [int(i) for i in raw_input().split()]
board = [['.' for _ in range(w)] for _ in range(h)]
walls = []

for i in xrange(h):
    inp = raw_input()
    for j in range(w):
        board[i][j] = inp[j]

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

f[0][0] = 1

for i in range(1, h):
    if board[i][0] == '#':
        f[i][0] = 0
    else:
        f[i][0] = f[i-1][0]

for i in range(1, w):
    if board[0][i] == '#':
        f[0][i] = 0
    else:
        f[0][i] = f[0][i-1]

for i in range(1, h):
    for j in range(1, w):
        if board[i][j] == '#':
            f[i][j] = 0
        else:
            f[i][j] = f[i-1][j] + f[i][j-1]

print f[-1][-1] % (int(1e9)+7)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
_map = [[1 if s=='.' else 0 for s in str(input())] for i in range(H)]
_mod = (10**9)+7
dp = [[0 for j in range(W)] for i in range(H)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if _map[i][j] == 1:
            if i < H-1 and _map[i+1][j] == 1:
                dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % _mod
            if j < W-1 and _map[i][j+1] == 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 sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

def tpsort(es, ordered = False):
    n = len(es)
    indgr = [0] * n
    for e in es:
        for u in e:
            indgr[u] += 1
    if ordered:
        from heapq import heappop, heappush
        st = []
        for v in range(n):
            if indgr[v] == 0: heappush(st, v)
        ret = []
        while st:
            v = heappop(st)
            ret.append(v)
            for u in es[v]:
                indgr[u] -= 1
                if indgr[u] == 0: heappush(st, u)
    else:
        st = [v for v in range(n) if indgr[v] == 0]
        ret = []
        while st:
            v = st.pop()
            ret.append(v)
            for u in es[v]:
                indgr[u] -= 1
                if indgr[u] == 0: st.append(u)
    if len(ret) == n:
        return ret
    else:
        return False

H, W = map(int, input().split())
f = [input() for i in range(H)]
mod = 10**9+7
dp = [[0]*W for i in range(H)]
dp[0][0] = 1
q = deque()
q.append((0, 0))
visit = [[1] * W for i in range(H)]
while q:
    i, j = q.popleft()
    if visit[i][j] == 0:
        continue
    visit[i][j] = 0
    if i+1 < H and visit[i+1][j] and f[i+1][j] == '.':
        q.append((i+1, j))
        dp[i+1][j] = (dp[i+1][j]+dp[i][j])%mod
    if j+1 < W and visit[i][j+1] and f[i][j+1] == '.':
        q.append((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 sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    H, W = map(int, input().split())
    chart = [[False] * (W + 2) for _ in range(H + 2)]

    for h in range(1, H + 1):
        line = input()
        for w, s in enumerate(line):
            if s == '.':
                chart[h][w + 1] = True

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

    for h in range(1, H + 1):
        for w in range(1, W + 1):
            if chart[h + 1][w]:
                dp[h + 1][w] = (dp[h + 1][w] + dp[h][w]) % MOD
            if chart[h][w + 1]:
                dp[h][w + 1] = (dp[h][w + 1] + dp[h][w]) % MOD

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

sol()

Submission status: Accepted

Solution code:
# 配るDP
def main():
  divisor = 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):
    ai = a[i]    
    dpi = dp[i]    
    if i + 1 < h:
      ai1 = a[i + 1]
      dpi1 = dp[i + 1]
    for j in range(w):
      if j + 1 < w and ai[j + 1] != '#':
        dpi[j + 1] = (dpi[j + 1] + dpi[j]) % divisor
      if i + 1 < h and ai1[j] != '#':
        dpi1[j] = dpi[j]
  print(dp[h - 1][w - 1])
main()

Submission status: Accepted

Solution code:
def main():
  divisor = 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
  dp0 = dp[0]
  a0 = a[0]
  for j in range(1, w):
    if a0[j] != '#':
      dp0[j] = dp0[j - 1]
  for i in range(1, h):
    dpi = dp[i]
    dpi1 = dp[i - 1]
    ai = a[i]
    if ai[0] != '#':
      dpi[0] = dpi1[0]
    for j in range(1, w):
      if ai[j] != '#':
        dpi[j] = (dpi1[j] + dpi[j - 1]) % divisor
  print(dp[h - 1][w - 1])
main()

Submission status: Accepted

Solution code:
def main():
  divisor = 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):
    ai = a[i]    
    dpi = dp[i]    
    if i + 1 < h:
      ai1 = a[i + 1]
      dpi1 = dp[i + 1]
    for j in range(w):
      if i + 1 < h and ai1[j] != '#':
        dpi1[j] = (dpi1[j] + dpi[j]) % divisor
      if j + 1 < w and ai[j + 1] != '#':
        dpi[j + 1] = (dpi[j + 1] + dpi[j]) % divisor
  print(dp[h - 1][w - 1])
main()

Submission status: Accepted

Solution code:
divisor = 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 i + 1 < h and a[i + 1][j] != '#':
      dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % divisor
    if j + 1 < w and a[i][j + 1] != '#':
      dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % divisor
print(dp[h - 1][w - 1])

Submission status: Accepted

Solution code:
divisor = 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
dp0 = dp[0]
a0 = a[0]
for j in range(1, w):
  if a0[j] != '#':
    dp0[j] = dp0[j - 1]
for i in range(1, h):
  dpi = dp[i]
  dpi1 = dp[i - 1]
  ai = a[i]
  if ai[0] != '#':
    dpi[0] = dpi1[0]
  for j in range(1, w):
    if ai[j] != '#':
      dpi[j] = (dpi1[j] + dpi[j - 1]) % divisor
print(dp[h - 1][w - 1])

Submission status: Accepted

Solution code:
h,w  = [int(j) for j in input().split()]
l = []
for i in range(h):
    l.append(input())
dp = dict()
dp[h-1,w-1]=1

for i in range(h)[::-1]:
    for j in range(w)[::-1]:
        if i==h-1 and j==w-1:
            continue
        if l[i][j] == "#":
            dp[i,j]=0
        else:
            flag =True
            if i+1<h and l[i+1][j]!="#":
                dp[i,j] = dp[i+1,j]
                flag = False
            if j+1<w and l[i][j+1]!="#":
                try:
                    dp[i,j]=dp[i,j+1]+dp[i,j]
                except:
                    dp[i,j]=dp[i,j+1]
                flag = False
            if flag:
                # print(i,j)
                dp[i,j]=0
# print(dp)
mod = 10**9+7
print(dp[0,0]%mod)

Submission status: Accepted

Solution code:
H, W = list(map(int, input().split()))
DP = [[0] * W] * H
for i, c in enumerate(input()):
    if i == 0:
        DP[0][0] = 1
    elif c == '.':
        DP[0][i] = DP[0][i-1]
    else:
        DP[0][i] = 0

for h in range(1, H):
    for i, c in enumerate(input()):
        if i == 0:
            if c == '.':
                DP[h][0] = DP[h-1][0]
            else:
                DP[h][0] = 0
        else:
            if c == '.':
                DP[h][i] = DP[h-1][i] + DP[h][i-1]
            else:
                DP[h][i] = 0

print(DP[-1][-1] % 1000000007)

Submission status: Accepted

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

def solve(h, w):
    prev = [None, 1] + [0]*(w-1)

    for _ in range(h):
        line = input()
        # print('line: ', line)
        next = [0] + [None]*w
        for j in range(w):
            if line[j] == '.':
                next[j+1] = (prev[j+1] + next[j]) % mod
            else:
                next[j+1] = 0
        prev = next

        # print(_, next)
    return next[-1]

print(solve(h, w))

"""
"""

Submission status: Accepted

Solution code:
import decimal,math
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 100
import sys
sys.setrecursionlimit(1000000)

n,m = map(int,raw_input().split())
mat=[]
mod=10**9+7
for i in range(n):
	p=raw_input()
	mat.append(p)
dp = [[0]*m for i in range(n)]
dp[0][0]=1
for j in range(1,m):
	if(mat[0][j]=='.'):
		dp[0][j]=dp[0][j-1]
for i in range(1,n):
	if(mat[i][0]=='.'):
		dp[i][0]=dp[i-1][0]
for i in range(1,n):
	for j in range(1,m):
		if(mat[i][j]=="."):
			dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
print (dp[-1][-1])%mod

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
MOD = 10**9 + 7

H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]

dp = [[0 for j in range(W)] for i in range(H)]  # 0-indexed
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[H-1][W-1] % MOD)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
buf = sys.stdin.buffer

import numpy as np
MOD = 10 ** 9 + 7

H,W = map(int,buf.readline().split())

grid = np.frombuffer(buf.read(),dtype='S1').reshape(H,-1)[:,:W]

MOD = 10 ** 9 + 7
dp = np.zeros(W, dtype=np.int64)
dp[0] = 1
for row in grid:
    wall = (row == b'#')
    # 上から落としてくる
    dp[wall] = 0
    # 左から右に
    np.cumsum(dp, out = dp)
    # 壁の補正
    sub = np.maximum.accumulate(dp * wall)
    dp -= sub
    dp %= MOD

answer = dp[-1]
print(answer)