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: Time Limit Exceeded

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

#nput = 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
div = (10 ** 9) + 7

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

if __name__=='__main__':
    H,W = map(int,input().split())
    
    t = [[""for _ in range(W)]for _ in range(H)]
    for i in range(H):
        line = input()
        for j in range(W):
            t[i][j] = line[j]
    np_map = np.array(t)
    dp = np.array([[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(np_map[i][j]=="."):
                dp[i+1][j] += dp[i][j]
                dp[i][j+1] += dp[i][j]
            else:
                dp[i][j] = 0
        
    print(dp[H-1][W-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	H_fix_2
# CreatedDate:  2020-05-19 21:18:06 +0900
# LastModified: 2020-05-19 23:40:56 +0900
#


import os
import sys
import numpy as np
#import pandas as pd


def main():
    h,w = map(int,input().split())
    dp = np.ones([h,w],dtype=np.int32)
    for i in range(h):
        dot_sharp = list(input())
        for j in range(w):
            if dot_sharp[j]=='#':
                dp[i,j]=0
    for i in range(h):
        if dp[i,0]==0:
            dp[(i+1):,0]=0
            break
    for j in range(w):
        if dp[0,j]==0:
            dp[0,j+1:]=0
    for i in range(1,h):
        for j in range(1,w):
            if dp[i,j]==0:
                continue
            dp[i,j]=(dp[i-1,j]+dp[i,j-1])%1000000007

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache, cmp_to_key
# from heapq import merge, heapify, heappop, heappush, nlargest, nsmallest
# from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, log
from collections import defaultdict as dd, deque, Counter as C, OrderedDict as od
# from itertools import combinations as comb, permutations as perm
# from bisect import bisect_left as bl, bisect_right as br, bisect
# from time import perf_counter
# from fractions import Fraction
sys.setrecursionlimit(pow(10, 6))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353
inf = int(1e20)
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(" ".join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


@lru_cache(None)
def recur(i=0, j=0):
    if i == n-1 and j == m-1:
        return int(mat[i][j] == '.')
    if i == n-1:
        if mat[i][j] == '#':
            return 0
        return recur(i, j+1)
    if j == m-1:
        if mat[i][j] == '#':
            return 0
        return recur(i+1, j)
    if mat[i][j] == '#':
        return 0
    answer = (recur(i+1, j) + recur(i, j+1)) % mod
    return answer


n, m = sp()
mat = []
for i in range(n):
    mat.append(list(data()))
out(recur())

Submission status: Time Limit Exceeded

Solution code:
from time import sleep
sleep(5)

Submission status: Time Limit Exceeded

Solution code:
from time import sleep
sleep(2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    H, W = map(int, input().split())
    A = [list(list(input())) for _ in range(H)]
    dp = np.zeros((H, W), dtype='uint64')
    dp[0][0] = 1

    for i in range(H):
        for j in range(W):
            if j + 1 < W and A[i][j + 1] == '.':
                dp[i, j + 1] += dp[i][j]
            if i + 1 < H and A[i + 1][j] == '.':
                dp[i + 1, j] += dp[i][j]
    print(int(dp[-1, -1] % 1000000007))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w = map(int,input().split())
stage = [["#" for x in range(w+2)] for x in range(h+2)]
for i in range(1,h+1):
    stage[i][1:w+1] = list(input())
dp = np.zeros([h+2,w+2],dtype=int)
dp[1][1] = 1
for j in range(1,h+1):
    for i in range(1,w+1):
        dp[j][i] = dp[j][i]%(10**9+7)
        if(stage[j+1][i] == "."):
            dp[j+1][i] += dp[j][i]
        if(stage[j][i+1] == "."):
            dp[j][i+1] += dp[j][i]
print(dp[h][w])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
mod = 10**9 + 7
H, W = map(int, input().split())
Maze = [[0]*W for _ in range(H)]
Memo = [[0]*W for _ in range(H)]
Memo[H-1][W-1] = 1
for i in range(H):
    S = input()
    for j in range(W):
        Maze[i][j] = S[j]

dx = [1, 0]
dy = [0, 1]


def clear_maze(x, y):
    if (x == W) and (y == H):
        return 1
    if Memo[y-1][x-1] != 0:
        return Memo[y-1][x-1]
    ans = 0
    for z in range(2):
        nx = x + dx[z]
        ny = y + dy[z]
        if (nx > W) or (ny > H):
            continue
        if Maze[ny-1][nx-1] == '.':
            ans += clear_maze(nx, ny)
    ans %= mod
    Memo[y-1][x-1] = ans
    return ans


print(clear_maze(1, 1) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def nop(h,w):
    if l[h-1][w-1]=='#':
        return 0
    if h==1:
        return left(w)
    elif w==1:
        return up(h)
    return nop(h-1,w)+nop(h,w-1)
def up(h):
    if l[h-1][0]=='#':
        return 0
    if h==1:
        return 1
    return up(h-1)
def left(w):
    if l[0][w-1]=='#':
        return 0
    if w==1:
        return 1
    return left(w-1)
h,w=map(int,input().split())
l=[list(input()) for _ in range(h)]
print(nop(h,w)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


class ModInt(int):
    
    MOD = 7

    def __new__(cls, x, *args, **kwargs):
        return super().__new__(cls, x % ModInt.MOD)

    def __add__(self, other):
        return ModInt(super().__add__(other) % ModInt.MOD)
    
    def __radd__(self, other):
        return ModInt(super().__radd__(other) % ModInt.MOD)
    
    def __mul__(self, other):
        return ModInt(super().__mul__(other) % ModInt.MOD)
    
    def __rmul__(self, other):
        return ModInt(super().__rmul__(other) % ModInt.MOD)
    
    def __pow__(self, other, *args):
        return ModInt(super().__pow__(other, ModInt.MOD))

    def __rpow__(self, other, *args):
        raise NotImplementedError()
    
    def __truediv__(self, other):
        return ModInt(super().__mul__(pow(other, ModInt.MOD-2, ModInt.MOD)))
    
    def __floordiv__(self, other):
        return self.__truediv__(other)
    
    def __rtruediv__(self, other):
        return ModInt(self.__pow__(ModInt.MOD-2).__mul__(other))
    
    def __rfloordiv__(self, other):
        return self.__rtruediv__(other)


def read():
    ModInt.MOD = 10**9+7
    H, W = map(int, input().strip().split())
    M = [[True for i in range(W)] for j in range(H)]
    for i in range(H):
        for j, x in enumerate(list(input().strip())):
            if x == '#':
                M[i][j] = False
            elif x == '.':
                M[i][j] = True
            else:
                raise ValueError()
    return H, W, M


def solve(H, W, M):
    dp = [[ModInt(0) for i in range(W+1)] for j in range(H+1)]
    dp[1][0] = 1
    for i in range(1, H+1):
        for j in range(1, W+1):
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) if M[i-1][j-1] else 0
    return dp[H][W]


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[[s=='.' for s in list(input())] for _ in range(h)]
#h,w=1000,1000
#a=[[True]*w]*h
mod=10**9+7
dp=np.zeros((h,w),np.int64)

novisited=np.array(a)
novisited[0,:]=False
novisited[:,0]=False
memo=np.zeros((h,w),np.int64)
for i in range(h):
      if a[i][0]:
            memo[i,0]=1
      else:
            break
for i in range(w):
      if a[0][i]:
            memo[0,i]=1
      else:
            break
def dp(i,j):
      if not novisited[i][j]:
            return memo[i,j]
      else:
            memo[i,j]=(dp(i-1,j)+dp(i,j-1))%mod
            novisited[i][j]=False
            return memo[i,j]

print(dp(h-1,w-1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[[s=='.' for s in list(input())] for _ in range(h)]
mod=10**9+7
dp=np.zeros((h,w),np.int64)
for i in range(h):
      if a[i][0]:
            dp[i,0]=1
      else:
            break
for j in range(w):
      if a[0][j]:
            dp[0,j]=1
      else:
            break
for i in range(1,h):
      for j in range(1,w):
            dp[i,j]=(dp[i-1,j]+dp[i,j-1])%mod if a[i][j] else 0
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import queue

H,W=map(int,input().split())
G=[list(str(input())) for _ in range(H)]
P=10**9+7


def sur(v):#v is tuple
    global H
    global W
    global G

    vx=v[0]
    vy=v[1]
    preE=[(vx+1,vy),(vx,vy+1)]
    E=[]
    for e in preE:
        if 0<=e[0]<H and 0<=e[1]<W:
            if G[e[0]][e[1]]=='.':
                E.append(e)
    return E

#DP[i][j]=(i+1,j+1)までの行き方の総数
DP=[[0]*W for row in range(H)]
DP[0][0]=1


#BFS
q=queue.Queue()
q.put((0,0))
L=set()
while not q.empty():
    now=q.get()
    for next in sur(now):
        DP[next[0]][next[1]]+=DP[now[0]][now[1]]
        DP[next[0]][next[1]]=DP[next[0]][next[1]]%P
        if next in L:
            continue
        q.put(next)
        L.add(next)
        #if next==(H-1,W-1):
            #print(now,next,L)

#for i in range(H):
    #string=''
    #for j in range(W):
        #if G[i][j]=='#':
            #string+=G[i][j]+' '
        #else:
            #string+=str(DP[i][j])+' '
    #print(string)
        
print(DP[H-1][W-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

H, W = map(int,input().split())
#A = [list(map(int,input().split())) for _ in range(H)]
A = np.array([list(input()) for _ in range(H)], 'U1')
eq = A == '.'

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

for i in range(H):
    for j in range(W):
        if eq[i][j]:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]
#            print(i,j,dp[i])
#            if i == 0 and j== 0:
#                dp[i+1][j+1] = 1
    dp[i+1] %= mod

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

Submission status: Time Limit Exceeded

Solution code:

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

H, W = map(int,input().split())
#A = [list(map(int,input().split())) for _ in range(H)]
A = np.array([list(input()) for _ in range(H)], 'U1')
eq = A == '.'

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

for i in range(H):
    for j in range(W):
        if eq[i][j]:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]
#            print(i,j,dp[i])
            if i == 0 and j== 0:
                dp[i+1][j+1] = 1
    dp[i+1] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

H, W = map(int,input().split())
#A = [list(map(int,input().split())) for _ in range(H)]
A = np.array([list(input()) for _ in range(H)], 'U1')
eq = A == '.'

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

for i in range(H):
    for j in range(W):
        if eq[i][j]:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]
#            print(i,j,dp[i])
            if i == 0 and j== 0:
                dp[i+1][j+1] = 1
    dp %= mod

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

H, W = map(int,input().split())
#A = [list(map(int,input().split())) for _ in range(H)]
A = np.array([list(input()) for _ in range(H)], 'U1')
eq = A == '.'

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

for i in range(1,H+1):
    prev = dp.copy()
    for j in range(1,W+1):
        if eq[i-1][j-1]:
            dp[j] = prev[j] + dp[j-1]
        else:
            dp[j] = 0
        dp %= mod

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

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

patterns = [[0 for _ in range(W)] for __ in range(H)]
searched = [[False for _ in range(W)] for __ in range(H)]
q = Queue()

div = 10**9+7

def search(x, y):
    if not (0 <= x < W and 0 <= y < H):
        return
    if searched[y][x]:
        return
    searched[y][x] = True
    if field[y][x] == '#':
        return
    res = 0
    if x > 0:
        res += patterns[y][x-1] % div
    if y > 0:
        res += patterns[y-1][x] % div
    patterns[y][x] = res % div
    q.put([x, y])
    return

patterns[0][0] = 1
q.put([0, 0])

while not searched[-1][-1]:
    x, y = q.get()
    search(x+1, y)
    search(x, y+1)
    
print(patterns[-1][-1] % div)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split())
A = [[1] * (W + 2)]
for _ in range(H):
    tmp = list(input())
    tmp = [1] + [0 if t == '.' else 1 for t in tmp] + [1]
    A.append(tmp)
A += [[1] * (W + 2)]
A = np.array(A)

MOD = 10**9 + 7

dp = np.zeros(A.shape, dtype='int')
dp[H][W] = 1
# dp[H][W]
# dp[i][j] : (i, j)マスから(H, W)マスへいくのに通れる経路の数
# dp[i][j] : dp[i + 1][j] + dp[i][j + 1] ?
for i in range(H + 1, 0, -1):
    for j in range(W + 1, 0, -1):
        if A[i][j] == 0:
            dp[i][j] = (dp[i][j] + dp[i + 1][j] + dp[i][j + 1]) % MOD
ans = dp[1][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

H, W = MAP()
a = ["#"*(W+2)]+["#"+input()+"#" for _ in range(H)] + ["#"*(W+2)]

dx = [1, 0]
dy = [0, 1]

comb = [[0]*(W+2) for _ in range(H+2)]
comb[1][1] = 1
q = deque()
q.append((1, 1))
while q:
    i, j = q.popleft()
    for k in range(2):
        y = i+dy[k]
        x = j+dx[k]
        if a[y][x] != "#":
            comb[y][x] = (comb[y][x] + comb[i][j])%mod
            if (y, x) not in q:
                q.append((y, x))
print(comb[H][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 10 ** 9 + 7

H, W = map(int, input().split())
count = np.ones(W, dtype=np.int)

row = input()
for w in range(1, W):
  if row[w] == '#':
    count[w:] = 0
    break

for h in range(1, H):
  row = input()
  if row[0] == '#':
    count[0] = 0
  for w in range(1, W):
    if row[w] == '#':
      count[w] = 0
    else:
      count[w] = (count[w-1] + count[w]) % MOD
print(count[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 10 ** 9 + 7

H, W = map(int, input().split())
count = np.ones(W, dtype=np.int)

row = input()
for w in range(1, W):
  if row[w] == '#':
    count[w:] = 0
    break

for h in range(1, H):
  row = input()
  if row[0] == '#':
    count[0] = 0
  period = 0
  for w in range(1, W):
    if row[w] == '#':
      count[period : w] = count[period : w].cumsum() % MOD
      count[w] = 0
      period = w + 1
  count[period:] = count[period:].cumsum() % MOD
print(count[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 10 ** 9 + 7

H, W = map(int, input().split())
count = np.ones((H, W), dtype=np.int)

row = input()
for w in range(1, W):
  if row[w] == '#':
    count[0, w:] = 0
    break

flag = True
for h in range(1, H):
  row = input()
  count[h] = count[h-1]
  if flag and row[0] == '#':
    count[h:, 0] = 0
    flag = False
  period = 0
  for w in range(1, W):
    if row[w] == '#':
      count[h, period : w] = count[h, period : w].cumsum() % MOD
      count[h, w] = 0
      period = w + 1
  count[h, period:] = count[h, period:].cumsum() % MOD
print(count[-1, -1])

Submission status: Time Limit Exceeded

Solution code:
R, C = tuple(map(int, input().split()))
grid = [list(input()) for _ in range(R)]
dp = [[0 for _ in range(C)] for _ in range(R)]
for row in range(R):
    if grid[row][0] != '#':
        dp[row][0] = 1
    else:
        break

for col in range(C):
    if grid[0][col] != '#':
        dp[0][col] = 1
    else:
        break


def simplify(paths, MAX=10 ** 9 + 7):
    while paths > MAX:
        paths -= MAX
    return paths


def gridpaths(R, C, grid):
    for row in range(1, R):
        for col in range(1, C):
            if grid[row][col] != '#':
                dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
        # print(dp)
    return simplify(dp[-1][-1])


print(gridpaths(R, C, grid))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dp = [[0]*w for _ in range(h)]
dp[0][0] = 1
reach = [[False]*w for _ in range(h)]
que = deque(())

que.append((0,0))

while que:
    i,j = que.popleft()
    if i < h-1 and a[i+1][j] == '.':
        if dp[i+1][j] == 0:
            que.append((i+1,j))
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= mod
    if j < w-1 and a[i][j+1] == '.':
        if dp[i][j+1] == 0:
            que.append((i,j+1))
        dp[i][j+1] += dp[i][j]
        dp[i][j+1] %= mod
print(dp[h-1][w-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros((H+1, W+1), dtype='int32')
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: Time Limit Exceeded

Solution code:
import numpy as np

H, W = [int(item) for item in input().split()]
grid = np.array([[item for item in input()] for _ in range(H)])

dp = np.zeros((H+1, W+1), dtype='int32')
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: Time Limit Exceeded

Solution code:
import numpy as np

H, W = [int(item) for item in input().split()]

grid = np.array([[item for item in input()] for _ in range(H)])
dp = np.zeros((H, W), dtype='int32')
max_num = 10**9 +7

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

    for i in range(H):
        for j in range(W):
            if grid[i, j] == '.' and i > 0 and j > 0:
                dp[i, j] = (dp[i-1, j] + dp[i, j-1]) % max_num
            elif grid[i, j] == '.' and i == 0 and j > 0:
                dp[i, j] = dp[i, j - 1] 
            elif grid[i, j] == '.' and j == 0 and i > 0:
                dp[i, j] = dp[i-1, j]

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = [int(item) for item in input().split()]

grid = np.array([[item for item in input()] for _ in range(H)])
dp = np.zeros((H, W), dtype='int32')

dp[0,0] = 1

for i in range(H):
    for j in range(W):
        if grid[i, j] == '.' and i > 0 and j > 0:
            dp[i, j] = (dp[i-1, j] + dp[i, j-1]) % (10**9 +7)
        elif grid[i, j] == '.' and i == 0 and j > 0:
            dp[i, j] = dp[i, j - 1] 
        elif grid[i, j] == '.' and j == 0 and i > 0:
            dp[i, j] = dp[i-1, j]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = [int(item) for item in input().split()]

grid = np.array([[item for item in input()] for _ in range(H)])
dp = np.zeros((H, W), dtype='int32')

dp[0,0] = 1

for i in range(H):
    for j in range(W):
        if grid[i, j] == '.' and i > 0 and j > 0:
            dp[i, j] = (dp[i-1, j] + dp[i, j-1]) % (10**9 +7)
        elif grid[i, j] == '.' and i == 0 and j > 0:
            dp[i, j] = dp[i, j - 1] % (10**9 +7)
        elif grid[i, j] == '.' and j == 0 and i > 0:
            dp[i, j] = dp[i-1, j] % (10**9 +7)

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

Submission status: Time Limit Exceeded

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)]
steplst =  [[]]
#stepdxy = [[1,0],[-1,0],[0,1],[0,-1]]
stepdxy = [[1,0],[0,1]]

def do_step(n):
    stepok = 0
    steplst.append([])
    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: Time Limit Exceeded

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
stepdic = {}
#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
                stepdic.setdefault(n,[]).append([x+dx,y+dy])
                stepok = 1
    if n-1 in stepdic.keys():
        for x,y in stepdic[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
                    stepdic.setdefault(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:
    stepn += 1

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jan 29 11:09:21 2020

@author: matsui
"""
import numpy as np

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

A=np.zeros([H,W])
for i in range(H):
    a=input()
    for j in range(W):
        if a[j]=='#': A[i,j]=1
        

dp=np.zeros([H,W])
if A[1,0]==0: dp[1,0]=1
if A[0,1]==0: dp[0,1]=1

for i in range(2,H):
    if A[i,0]==0 :
        dp[i,0]=dp[i-1,0]
      
for i in range(2,W):
    if A[0,i]==0 :
        dp[0,i]=dp[0,i-1]
      
for i in range(1,H):
    for j in range(1,W):
        if A[i,j]==0:
            if A[i-1,j]==0:dp[i,j]+=dp[i-1,j]
            if A[i,j-1]==0:dp[i,j]+=dp[i,j-1]
            #dp[i,j]=dp[i-1,j]+dp[i,j-1]
      
      
ans=int(dp[-1,-1]%(1e9+7))
#print(A)
#print(dp)
print(ans)

Submission status: Time Limit Exceeded

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)]
seen = [[False]*(W+2) for _ in range(H+2)]

cost[1][1] = 1
seen[1][1] = True
node = deque([(1, 1)])
while node:
    x, y = node.popleft()
    c = cost[x][y]

    if grid[x+1][y] == 1:
        cost[x+1][y] += c
        cost[x+1][y] %= mod
        if not seen[x+1][y]:
            seen[x+1][y] = True
            node.append((x+1, y))

    if grid[x][y + 1] == 1:
        cost[x][y+1] += c
        cost[x][y+1] %= mod
        if not seen[x][y+1]:
            seen[x][y+1] = True
            node.append((x, y+1))


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

Submission status: Time Limit Exceeded

Solution code:
import random

import sys
sys.setrecursionlimit(100000000)

# N, W = 100, 20000
# W_V = [[random.randint(1,1000000), random.randint(1,1000)] for i in range(N)]
H, W = map(int, raw_input().split())
MAZE = [raw_input() for i in range(H)]
path_count_cache = {}
BLOCK = '#'

def get_path_count(x, y):
    if (x, y) in path_count_cache:
        return path_count_cache[x,y]

    if x >= W or y >= H or MAZE[y][x] == BLOCK:
        return 0

    if x == W - 1 and y == H - 1:
        return 1

    all_path = (get_path_count(x+1, y) + get_path_count(x, y+1))

    if all_path >=  1000000007:
        all_path -=  1000000007

    path_count_cache[x, y] = all_path
    return all_path
  
print get_path_count(0, 0)

Submission status: Time Limit Exceeded

Solution code:
import random

import sys
sys.setrecursionlimit(100000000)

# N, W = 100, 20000
# W_V = [[random.randint(1,1000000), random.randint(1,1000)] for i in range(N)]
H, W = map(int, raw_input().split())
MAZE = [raw_input() for i in range(H)]
path_count_cache = {}
BLOCK = '#'

def get_path_count(x, y):
    if (x, y) in path_count_cache:
        return path_count_cache[x,y]

    if x >= W or x < 0 or y >= H or y < 0:
        return 0

    if MAZE[y][x] == BLOCK:
        return 0

    if x == W - 1 and y == H - 1:
        return 1

    all_path = (get_path_count(x+1, y) + get_path_count(x, y+1)) % 1000000007

    path_count_cache[x, y] = all_path
    return all_path


print get_path_count(0, 0)

Submission status: Time Limit Exceeded

Solution code:
a, b = list(map(int, input().split()))
grid = list()
grid.append([-1 for _ in range(b + 2)])
for t in range(0, a):
    grid.append([-1])
    line = list(input())
    for k in range(len(line)):
        if line[k] == '#':
            grid[t + 1] += [-1]
        else:
            grid[t + 1] += [0]
    grid[t + 1] +=[-1]
grid.append([-1 for _ in range(b + 2)])
check_list = [[1, 1]]
while len(check_list) != 0:
    new_check_list = []
    for x, y in check_list:
        if grid[x + 1][y] != -1:
            grid[x + 1][y] += 1
            new_check_list.append([x + 1, y])
        if grid[x][y + 1] != -1:
            grid[x][y + 1] += 1
            new_check_list.append([x, y + 1])
    check_list = new_check_list
print(grid[-2][-2])

Submission status: Time Limit Exceeded

Solution code:
a, b = list(map(int, input().split()))
grid = list()
grid.append([-1 for _ in range(b + 2)])
grid.append([-1] + [1] + [0 for _ in range(b - 1)] + [-1])
for _ in range(a - 1):
    grid.append([-1] + [0 for _ in range(b)] + [-1])
grid.append([-1 for _ in range(b + 2)])
for t in range(a):
    line = list(input())
    for k in range(len(line)):
        if line[k] == '#':
            grid[t + 1][k + 1] = -1
check_list = [[1, 1]]
while len(check_list) != 0:
    new_check_list = []
    for x, y in check_list:
        if grid[x + 1][y] != -1:
            grid[x + 1][y] += 1
            new_check_list.append([x + 1, y])
        if grid[x][y + 1] != -1:
            grid[x][y + 1] += 1
            new_check_list.append([x, y + 1])
    check_list = new_check_list
print(grid[-2][-2])