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: Wrong Answer

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: Wrong Answer

Solution code:
h,w =list(map(int,input().split()))
a = [[i for i in input()] for j 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 and j==0: pass
		elif a[i][j]!="#":
			if i==0 : dp[i][j]=dp[i][j-1]
			elif j==0: dp[i][j]=dp[i-1][j]
			else:dp[i][j]=dp[i-1][j]+dp[i][j-1]
			
		else: dp[i][j]=0
print(dp[h-1][w-1])

Submission status: Wrong Answer

Solution code:
r,c=map(int,input().split())
dp=[[0]*(c+1) for i in range(r+1)]
a=[]
for i in range(r):
    a.append(input())
dp[0][1]=1
for i in range(1,r+1):
    for j in range(1,c+1):
        if(a[i-1][j-1]=='.'):
            dp[i][j]=dp[i-1][j]+dp[i][j-1]
print(dp[r][c])

Submission status: Wrong Answer

Solution code:
import fileinput

def find_path_count(n, m, wall_set):
    modulo = 10**9 + 7
    path_table = []
    def get_path_count(x, y):
        if x < 0 or y < 0 or (x, y) in wall_set:
            return 0
        return path_table[x][y]

    for x in range(n):
        path_table.append([0] * m)
        for y in range(m):
            if x == 0 and y == 0:
                path_table[x][y] = 1
            else:
                path_table[x][y] = (get_path_count(x - 1, y) + get_path_count(x, y - 1)) % modulo

    return path_table[n - 1][m - 1]

def parse_vall_set(map_strings):
    wall_set = set()
    for x, s in enumerate(map_strings):
        for y, ch in enumerate(s):
            if ch == "#":
                wall_set.add((x, y))
    return wall_set


inp = fileinput.FileInput()
n, m = inp.readline().split(" ")
n, m = int(n), int(m)
print(n, m)
map_strings = []
for _ in range(n):
    map_strings.append(inp.readline())

print(find_path_count(n, m, parse_vall_set(map_strings)))

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
m=[[0]*(w+2) for i in range(h+2)]
for i in range(h):
    for (j,s) in enumerate(input()):
        m[i+1][j+1]=0 if s=='#' else 1

for i in range(1,h+1):
    for j in range(1,w+1):
        if i*j==1:
            0
        elif m[i][j]!=0:
            m[i][j]=m[i-1][j]+m[i][j-1]
        
print(m[h][w])

Submission status: Wrong Answer

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

grid = [list(input()) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            grid[i][j] = 1
            continue

        if grid[i][j] == "#":
            grid[i][j] = 0
            continue

        if i == 0:
            grid[i][j] = grid[i][j-1]
            continue

        if j == 0:
            grid[i][j] = grid[i-1][j]
            continue

        grid[i][j] = grid[i-1][j] + grid[i][j-1]

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

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7

H, W = map(int, input().split())
A = [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 A[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] % mod

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

Submission status: Wrong Answer

Solution code:
height, width = (int(i) for i in input().split(" "))

# grid = [[None for _ in range(0, width)] for _ in range(0, height)] 
# build the input array
grid = []
for heightInd in range(0, height):
    new_row_string = input()
    new_array = list(new_row_string)
    grid.append(new_array)

# build the maxpaths
max_paths = [[0 for _ in range(0, width)] for _ in range(0, height)]

if grid[0][0] == "#" or grid[height-1][width -1] == "#":
    print("0")

max_paths[0][0] = 1

# populate the top row and first column
for colIndex in range(1, width):
    if grid[0][colIndex] == "#":
        break
    else:
        max_paths[0][colIndex] = 1

for rowInd in range(1, height):
    if grid[rowInd][0] == "#":
        break
    else:
        max_paths[rowInd][0] = 1

for rowIndex in range(1, height):
    for colIndex in range(1, width):
        if grid[rowIndex][colIndex] is not "#":
            max_paths[rowIndex][colIndex] = max_paths[rowIndex - 1][colIndex] + max_paths[rowIndex][colIndex - 1]

print(max_paths[height - 1][width - 1])

Submission status: Wrong Answer

Solution code:
height, width = (int(i) for i in input().split(" "))

# grid = [[None for _ in range(0, width)] for _ in range(0, height)] 
# build the input array
grid = []
for heightInd in range(0, height):
    new_row_string = input()
    new_array = list(new_row_string)
    grid.append(new_array)

# build the maxpaths
max_paths = [[0 for _ in range(0, width)] for _ in range(0, height)]

if grid[0][0] == "#" or grid[height-1][width -1] == "#":
    print("Total is 0")

max_paths[0][0] = 1

# populate the top row and first column
for colIndex in range(1, width):
    if grid[0][colIndex] == "#":
        break
    else:
        max_paths[0][colIndex] = 1

for rowInd in range(1, height):
    if grid[rowInd][0] == "#":
        break
    else:
        max_paths[rowInd][0] = 1

for rowIndex in range(1, height):
    for colIndex in range(1, width):
        if grid[rowIndex][colIndex] is not "#":
            max_paths[rowIndex][colIndex] = max_paths[rowIndex - 1][colIndex] + max_paths[rowIndex][colIndex - 1]

print(max_paths[height - 1][width - 1])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
dp = [[0]*(w+1) for i in range(h+1)]
a = list(input() for _ in range(h))
dp[0][0] = 1
#配るDP
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]
print(dp[h-1][w-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))
a = [([c=="#" for c in input()] + [0]) for _ in range(H)] + [[0]*(W+1)]

mod = 10**9+7
ij = [[H-1-1,W-1],[H-1,W-1-1]]
a[H-1][W-1] = 1
cnt = 0
while 1:
    i,j = ij[cnt]
    if a[i][j] is False:
        a[i][j] = (a[i+1][j] + a[i][j+1])%mod
        if i>0:
            ij.append([i-1,j])
        if j>0:
            ij.append([i,j-1])
    elif a[i][j] is True:
        a[i][j] = 0
    cnt += 1
    if len(ij) <= cnt:
        break
if a[0][0] is False:
    a[0][0] = 0
print(a[0][0])

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))
a = [([c=="#" for c in input()] + [0]) for _ in range(H)] + [[0]*(W+1)]

mod = 10**9+7
ij = [[H-1-1,W-1],[H-1,W-1-1]]
a[H-1][W-1] = 1
cnt = 0
while 1:
    i,j = ij[cnt]
    if a[i][j] is False:
        a[i][j] = a[i+1][j] + a[i][j+1]
        if a[i][j] >= mod:
            a[i][j] %= mod
        if i>0 and type(a[i-1][j])==bool:
            ij.append([i-1,j])
        if j>0 and type(a[i][j-1])==bool:
            ij.append([i,j-1])
    elif a[i][j] is True:
        a[i][j] = 0
    cnt += 1
    if len(ij) <= cnt:
        break
if a[0][0] is False:
    a[0][0] = 0
print(a[0][0])

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))
a = [([c=="#" for c in input()] + [0]) for _ in range(H)] + [[0]*(W+1)]

mod = 10**9+7
ij = [[H-1-1,W-1],[H-1,W-1-1]]
a[H-1][W-1] = 1
while ij != []:
    i,j = ij[0]
    if a[i][j] is False:
        a[i][j] = a[i+1][j] + a[i][j+1]
        if a[i][j] > mod:
            a[i][j] %= mod
        if i>0:
            ij.append([i-1,j])
        if j>0:
            ij.append([i,j-1])
    elif a[i][j] is True:
        a[i][j] = 0
    ij = ij[1:]
if a[0][0] is False:
    a[0][0] = 0
print(a[0][0])

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
mod=10e9+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]
            if dp[i][j]>=mod:
                dp[i][j]-=mod
print(dp[-1][-1])

Submission status: Wrong Answer

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]
print(dp[h-1][w-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w = map(int,input().split())
g = [list(input()) for _ in range(h)]
#print(g)
dp = np.zeros((h,w))
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: Wrong Answer

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)]*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 = [[0]*(W+1)]*(H+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]


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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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]) % (10 ** 9 + 7)

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

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7


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

fields = []
for _ in xrange(H) : 
    fields.append(list(raw_input().strip()))

dp = [[0 if (x != 0 and y != 0) or fields[y][x] == '#' else 1 for x in xrange(W)] for y in xrange(H)]


for r in xrange(1, H) : 
    for c in xrange(1, W) : 
        if fields[r][c] == '#' : 
            continue

        dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

print dp[-1][-1] % MOD

Submission status: Wrong Answer

Solution code:



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

fields = []
for _ in xrange(H) : 
    fields.append(list(raw_input().strip()))

dp = [[0 if (x != 0 and y != 0) or fields[y][x] == '#' else 1 for x in xrange(W)] for y in xrange(H)]


for r in xrange(1, H) : 
    for c in xrange(1, W) : 
        if fields[r][c] == '#' : 
            continue

        dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

print dp[-1][-1]

Submission status: Wrong Answer

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

A=[["#"]*(w+1)]+[["#"]+list(input()) for i in range(h)]
C=[[0]*(w+1) for i in range(h+1)]
C[1][1]=1
for i in range(1,h+1):
  for j in range(1,w+1):
    if A[i][j]=='.' and not (i==1 and j==1):
      C[i][j] = C[i-1][j]+C[i][j-1]
print(C[-1][-1])

Submission status: Wrong Answer

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

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

flagH = 0
flagW = 0

for i in range(H):
  if a[i][0]=="." and flagH==0:
    dp[i][0]=1
  else:
    dp[i][0]=0
    flagH=1

for j in range(W):
  if a[0][j]=="." and flagW==0:
    dp[0][j]=1
  else:
    dp[0][j]=0
    flagW=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]%7000000000)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

dp = [[0]*W for _ in range(H)]
for w in range(W):
    if a[0][w]=="#":
        break
    dp[0][w] = 1
for h in range(H):
    if a[h][0]=="#":
        break
    dp[h][0] = 1

        
for h in range(H):
    for w in range(W):
        if h+1<H and w+1<W and a[h+1][w+1]==".":
            dp[h+1][w+1] = dp[h][w+1] + dp[h+1][w]
    #print(dp)
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
M = []
for i in range(H):
  M.append(input())
d = {}
for j in range(W):
  d[(1,j+1)] = 1
for k in range(H):
  d[(k+1,1)] = 1
for l in range(1,H):
  for m in range(1,W):
    if M[l][m]==".":
      d[(l+1,m+1)]=(d[(l,m+1)]+d[(l+1,m)])%(1000000007)
    else :
      d[(l+1,m+1)] = 0
print(d[(H,W)])

Submission status: Time Limit Exceeded

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

mod = 10**9+7

def dfs(x,y):
    if not(0<=x<H) or not(0<=y<W):
        return
    if  maze[x][y]=="#":
        return
    
    if x==H-1 and y==W-1:
        return
        
    dh = [1,0]
    dw = [0,1]
    
    for i,j in zip(dh,dw):
        if (0<=x+i<H) and (0<=y+j<W):
            if maze[x+i][y+j]!="#":
                dp[x+i][y+j] += 1
                dp[x+i][y+j] %= mod
        dfs(x+i,y+j)

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

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

dfs(0,0)
print(dp[H-1][W-1])

Submission status: Time Limit Exceeded

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

mod = 10**9+7

def dfs(x,y):
    if not(0<=x<H) or not(0<=y<W):
        return
    if  maze[x][y]=="#":
        return
    
    if x==H-1 and y==W-1:
        return
        
    dh = [1,0]
    dw = [0,1]
    
    for i,j in zip(dh,dw):
        if (0<=x+i<H) and (0<=y+j<W):
            if maze[x+i][y+j]!="#":
                dp[x+i][y+j] += 1
                dp[x+i][y+j] %= mod
        dfs(x+i,y+j)

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

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

dfs(0,0)
print(dp[H-1][W-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)

def grid(y,x):
    global dp
    if mp[y][x]!='#' and dp[y][x]==0:
        dp[y][x]=grid(y-1,x)+grid(y,x-1)
    return dp[y][x]

H,W=map(int,input().split())
mp=[['#']*(W+1)]
for _ in range(H):
    mp.append(['#']+list(input()))
mp.append(['#']*(W+1))

dp=[[0]*(W+1) for _ in range(H+1)]
dp[1][1]=1
grid(H,W)
print(dp[H][W]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)

def grid(y,x):
    global dp
    if mp[y][x]!='#' and dp[y][x]==0:
        dp[y][x]=grid(y-1,x)+grid(y,x-1)
    return dp[y][x]

H,W=map(int,input().split())
mp=[['#']*(W+1)]
for _ in range(H):
    mp.append(['#']+list(input()))
mp.append(['#']*(W+1))

dp=[[0]*(W+1)for _ in range(H+1)]
dp[1][1]=1
grid(H,W)
print(dp[H][W]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)

def grid(y,x):
    global dp
    if mp[y][x]!='#' and dp[y][x]==0:
        for dx,dy in [(-1,0),(0,-1)]:
            nx,ny=x+dx,y+dy
            dp[y][x]+=grid(ny,nx)
    return dp[y][x]


H,W=map(int,input().split())
mp=[['#']*(W+2)]
for _ in range(H):
    mp.append(['#']+list(input())+['#'])
mp.append(['#']*(W+2))

dp=[[0]*(W+2)for _ in range(H+2)]
dp[1][1]=1
grid(H,W)
print(dp[H][W]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)

def grid(y,x):
    global dp
    if mp[y][x]!='#' and dp[y][x]==0:
        for dx,dy in [(-1,0),(0,-1)]:
            nx,ny=x+dx,y+dy
            dp[y][x]+=grid(ny,nx)
            dp[y][x]%=(10**9+7)
    return dp[y][x]


H,W=map(int,input().split())
mp=[['#']*(W+2)]
for _ in range(H):
    mp.append(['#']+list(input())+['#'])
mp.append(['#']*(W+2))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

mod = 10**9+7

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]

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

D = deque()
D.append((0, 0))

dxdy = [(0, 1), (1, 0)]

appended =  [[False]*w for _ in range(h)]
appended[0][0] = True
while D:
  p = D.popleft()
  if p == (h-1, w-1):
    break
  for k in range(2):
    nx = p[0] + dxdy[k][0]
    ny = p[1] + dxdy[k][1]
    if 0<=nx<h and 0<=ny<w and maze[nx][ny]==".":
      cnt[nx][ny] += cnt[p[0]][p[1]]
      cnt[nx][ny] %= mod
      if appended[nx][ny]==False:
        D.append((nx, ny))
        appended[nx][ny] = True

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W = map(int, input().split())
m = 10**9+7
index_lst = []
grid_0 = [0] * (W+1)
grid_0[1] = 1
for _ in range(1, H+1):
    index_lst = [i for i, j in enumerate(input(), 1) if j == '#']
    grid_1 = [0] * (W+1)
    for w in range(1, W+1):
      if w not in index_lst:
      	grid_1[w] = (grid_1[w-1] + grid_0[w]) % m
    grid_0 = grid_1

print(grid_0[-1])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
index_lst = []
grid_0 = [0] * (W+1)
grid_0[1] = 1
for _ in range(1, H+1):
    index_lst = [i for i, j in enumerate(input(), 1) if j == '#']
    grid_1 = [0] * (W+1)
    for w in range(1, W+1):
      if w not in index_lst:
      	grid_1[w] = grid_1[w-1] + grid_0[w]
    grid_0 = grid_1

print(grid_0[-1] % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1

INF = 0
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (0,1)}
init_q =[]
mod = 10**9+7

from collections import deque

def bfs(init):
    next_q = deque([])
    for i in init:
        next_q.append(i)
        Dist[i[0]][i[1]] = 1

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h,w = next_q.popleft()
        if Seen[h][w]==1:
            continue
        Seen[h][w]=1
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.':
                next_q.append([hs,ws])
                Dist[hs][ws] += Dist[h][w]
                Dist[hs][ws] %= mod
    return Dist

def main():
    #固定
    init_q.append([sth, stw])

    ret = bfs(init_q)
    print(ret[glh][glw])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(2e6))

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

dp=[[0]*w for _ in range(h)]
z=[[0]*w for _ in range(h)]
dp[h-1][w-1]=1
z[h-1][w-1]=1
def c(i,j):
    if z[i][j]!=0:
        return dp[i][j]
    if 1<=i+1<=h-1 and 0<=j<=w-1:
        if a[i+1][j]!="#":
            dp[i][j]+=c(i+1,j)
        else:
            z[i+1][j]=1
    if 1<=j+1<=w-1 and 0<=i<=h-1:
        if a[i][j+1]!="#":
            dp[i][j]+=c(i,j+1)
        else:
            z[i][j+1]=1
    z[i][j]=1
    return dp[i][j]
print(c(0,0)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(2e6))
h,w=map(int,input().split())
a=[]
for _ in range(h):
    a.append(list(input()))

dp=[[0]*w for _ in range(h)]
z=[[0]*w for _ in range(h)]
dp[h-1][w-1]=1
z[h-1][w-1]=1
def c(i,j):
    if z[i][j]!=0:
        return dp[i][j]
    if 1<=i+1<=h-1 and 0<=j<=w-1:
        if a[i+1][j]!="#":
            dp[i][j]+=c(i+1,j)
    if 1<=j+1<=w-1 and 0<=i<=h-1:
        if a[i][j+1]!="#":
            dp[i][j]+=c(i,j+1)
    z[i][j]=1
    return dp[i][j]
print(c(0,0)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(2e6))
h,w=map(int,input().split())
a=[]
for _ in range(h):
    a.append(list(input()))
    
dp=[[0]*w for _ in range(h)]
z=[[0]*w for _ in range(h)]
dp[h-1][w-1]=1
def c(i,j):
    if z[i][j]!=0:
        return dp[i][j]
    if 1<=i+1<=h-1 and 0<=j<=w-1:
        if a[i+1][j]!="#":
            dp[i][j]+=c(i+1,j)
    if 1<=j+1<=w-1 and 0<=i<=h-1:
        if a[i][j+1]!="#":
            dp[i][j]+=c(i,j+1)
    z[i][j]=1
    return dp[i][j]
print(c(0,0)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10**9 + 7
H, W = map(int, input().split())
field = [['#'] * (W + 2)]
for i in range(H):
    field.append(list('#' + input() + '#'))
field.append(['#'] * (W + 2))

dp = np.zeros((H+2, W+2),dtype=int)
dp[H][W] = 1

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

print(dp[1][1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10**9 + 7
H, W = map(int, input().split())
field = [['#'] * (W + 2)]
for i in range(H):
    field.append(list('#' + input() + '#'))
field.append(['#'] * (W + 2))

dp = np.zeros((H+2, W+2),dtype=int)
dp[H][W] = 1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10**9 + 7
H, W = map(int, input().split())
field = [['#'] * (W + 2)]
for i in range(H):
    field.append(list('#' + input() + '#'))
field.append(['#'] * (W + 2))

dp = np.zeros((H+2, W+2),dtype=int)
dp[H][W] = 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

sys.setrecursionlimit(10**6)
# def solve():
# 	n, m = read()
# 	graph = [[] for i in range(n+1)]
# 	for _ in range(m):
# 		u, v = read()
# 		graph[u].append(v)
# 	visited = [0 for i in range(n+1)]
# 	def dfs(node):
# 		if visited[node]:
# 			return(visited[node])
# 		if not graph[node]:
# 			visited[node] = 0
# 			return(0)
# 		m = 0
# 		for i in graph[node]:
# 			m = max(m, dfs(i))
# 		visited[node] = 1 + m#ax(dfs(i) for i in graph[node])
# 		# print(node, visited[node])
# 		return(visited[node])

# 	ans = 0
# 	for i in range(1, n+1):
# 		ans = max(ans, dfs(i))
# 	# print(visited)
# 	print(ans)


def grid():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	# dic = {}
	dp = [-1]*m*n
	# print(dp, len(dp))
	def count_paths(i, j):
		# key = str(i)+"-"+str(j)
		# if key in dic:
		# 	return(dic[key])
		key = (i*m + j)
		# print(key)
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "#":
			dp[key] = 0
			return(0)
		if dp[key] > -1:
			return(dp[key])
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		# dic[key] = paths
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))

def grid2():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	dp = {}
	# print(dp, len(dp))
	def count_paths(i, j):
		key = str(i)+"-"+str(j)
		if key in dp:
			return(dp[key])
		# key = (i*m + j)
		# print(key)
		if key in dp:
			return(dp[key])
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "#":
			dp[key] = 0
			return(0)
		
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		# dic[key] = paths
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))



if __name__ == "__main__":
	# solve()
	grid2()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H,W = map(int,input().split())
grid = [list(input()) for i in range(H)]
dp = np.zeros([H + 1,W + 1],dtype = int)
dp[0][0] = 1
mod = (10 ** 9) + 7

for i in range(H):
  for j in range(W):
    if i > 0 or j > 0:
      if grid[i][j] == "#":
        dp[i][j] = 0
      else:
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from functools import lru_cache
from collections import deque

#input = sys.stdin.readline
#sys.setrecursionlimit(10 ** 5)

H,W = map(int,input().split())
grid = [list(input()) for i in range(H)]
dp = np.zeros([H + 1,W + 1],dtype = int)
dp[0][0] = 1
mod = (10 ** 9) + 7

def plus(a,b):
  a += b
  if a > mod:
    a %= mod
  return a

for i in range(H):
  for j in range(W):
    if i + 1 < H and grid[i + 1][j] == ".":
      dp[i + 1][j] = plus(dp[i + 1][j],dp[i][j])
      
    if j + 1 < W and grid[i][j + 1] == ".":
      dp[i][j + 1] = plus(dp[i][j + 1],dp[i][j])

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