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 collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, readline().split()))
    a = [list(str(readline().rstrip().decode('utf-8'))) for _ in range(h)]

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    cl = collections.defaultdict(int)
    cl[0, 0] = 1
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            for xv, yv in [[x + 1, y], [x, y + 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if a[xv][yv] != "#":
                        ql.append([cost + 1, xv, yv])
                        cl[xv, yv] = cl[x, y]
                        a[xv][yv] = "#"
                    else:
                        cl[xv, yv] += cl[x, y]
                        cl[xv, yv] % mod
        else:
            break
    print(cl[h-1, w-1] % mod)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, readline().split()))
    a = [list(str(readline().rstrip().decode('utf-8'))) for _ in range(h)]

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[0, 0]
    cl = collections.defaultdict(int)
    cl[0, 0] = 1
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            for xv, yv in [[x + 1, y], [x, y + 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq and a[xv][yv] != "#":
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv] = cost + 1
                        cl[xv, yv] = cl[x, y]
                    else:
                        cl[xv, yv] += cl[x, y]
                        cl[xv, yv] % mod
        else:
            break
    print(cl[h-1, w-1] % mod)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [list(str(input().rstrip('\n'))) for _ in range(h)]

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    fq[0, 0] = 1
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            for xvv, yvv in [[xv + 1, yv], [xv, yv + 1]]:
                if 0 <= xvv < h and 0 <= yvv < w:
                    if (xvv, yvv) not in fq and a[xvv][yvv] != "#":
                        ql.append([cost + 1, xvv, yvv])
                        fq[xvv, yvv] = fq[xv, yv]
                    else:
                        fq[xvv, yvv] += fq[xv, yv]
        else:
            break
    print(fq[h-1, w-1] % mod)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import queue

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

a = [list(input()) for _ in range(H)]

Q = queue.Queue()
Q.put([0,0])
a[0][0] = 1

while not Q.empty():
    i, j = Q.get()
    if j < W - 1:
        if a[i][j+1] == '.':
            if i == 0:
                U = 0
            elif a[i-1][j+1] == '#' or a[i-1][j+1] == '.':
                U = 0
            else:
                U = a[i-1][j+1]
            a[i][j+1] = a[i][j] + U
            Q.put([i,j+1])
    if i < H - 1:
        if a[i+1][j] == '.':
            if j == 0:
                L = 0
            elif a[i+1][j-1] == '#' or a[i+1][j-1] == '.':
                L = 0
            else:
                L = a[i+1][j-1]
            a[i+1][j] = a[i][j] + L
            Q.put([i+1,j])

if a[H-1][W-1] == '.':
    print(0)
else:
    print(a[H-1][W-1] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import *
from numpy import zeros
sys.setrecursionlimit(200000000)
mod=10**9+7

def rec(i, j):
  if dp[i][j] != 0:
    return dp[i][j]
  res = 0
  if(i >= 1 and j >= 1):
    res = 1
    if a[i-1][j-1] == "#":
      res = 0
    else:
      res = rec(i-1, j) + rec(i, j-1)
  dp[i][j] = res%mod
  return dp[i][j]


#入力
n,m = (int(x) for x in input().split())
a = [input() for _ in range(n)]

dp = zeros((n+1, m+1))
dp[1][1] = 1
ans = rec(n, m)
#出力
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import *
import numpy as np
sys.setrecursionlimit(200000)
mod=10**9+7

def rec(i, j):
  if dp[i][j] != 0:
    return dp[i][j]
  res = 0
  if(i >= 1 and j >= 1):
    res = 1
    if a[i-1][j-1] == "#":
      res = 0
    else:
      res = rec(i-1, j) + rec(i, j-1)
  dp[i][j] = res%mod
  return dp[i][j]


#入力
n,m = (int(x) for x in input().split())
a = [input() for _ in range(n)]

dp = np.full((n+1, m+1), 0)
dp[1][1] = 1
ans = rec(n, m)
#出力
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

H,W = inpl()
MAP = [['#']*(W+2)] + [['#']+list(input())+['#'] for y in range(H)] + [['#']*(W+2)]

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

for x in range(1,W+1):
    for y in range(1,H+1):
        if MAP[y][x] == '.':
            dp[y][x] = (dp[y-1][x] + dp[y][x-1])%mod

print(dp[H][W])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
DVSR = 1000000007
def LI(): return [int(x) for x in input().split()]
H,W=LI()
MP=[input() for _ in range(H)]
MEMO=[[(-1,0)]*W for _ in range(H)]
MEMO[0][0] = (0,1)
QU=deque([])

QU.append((0,0,0))
IT=[(1,0),(0,1)]
while QU:
    i,j,cost = QU.popleft()
    cost+=1
    pat = MEMO[i][j][1]
    for dy, dx in IT:
        ny, nx = i+dy, j+dx
        if ny < H and ny >= 0 and nx < W and nx >= 0 and MP[ny][nx] == '.':
            cost2, pat2 = MEMO[ny][nx]
            if cost2 == -1:
                MEMO[ny][nx] = (cost, pat)
                QU.append((ny,nx,cost))
            elif cost2 == cost:
                _pat = (pat+pat2)%DVSR
                MEMO[ny][nx] = (cost,_pat)

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

Submission status: Time Limit Exceeded

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

import numpy as np

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

grid = np.array([list(input()) for _ in range(H)])

# dp[h][w] = (0,0) から (h,w) までの経路の本数
dp = np.zeros((H, W))
# 初期値
dp[0][0] = 1

# mod用
MOD_INT = 10 ** 9 + 7

for h in range(H):
    for w in range(W):
        # 右が範囲内の空マスなら現在マスの経路数を足す
        if w + 1 < W and grid[h][w + 1] == ".":
            # modを取って更新
            dp[h][w + 1] += np.mod(dp[h][w], MOD_INT)
        # 下が範囲内の空マスなら現在マスの経路数を足す
        if h + 1 < H and grid[h + 1][w] == ".":
            # modを取って更新
            dp[h + 1][w] = np.mod(dp[h][w], MOD_INT)

ans = np.mod(dp[H - 1][W - 1], MOD_INT)
print(int(ans))

Submission status: Time Limit Exceeded

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

import numpy as np

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

grid = np.array([list(input()) for _ in range(H)])

# dp[h][w] = (0,0) から (h,w) までの経路の本数
dp = np.zeros((H, W))
# 初期値
dp[0][0] = 1

# mod用
MOD_INT = 1000000007

for h in range(H):
    for w in range(W):
        # 右が範囲内の空マスなら現在マスの経路数を足す
        if w + 1 < W and grid[h][w + 1] == ".":
            dp[h][w + 1] += dp[h][w]
            # modを取って更新
            dp[h][w + 1] = np.mod(dp[h][w + 1], MOD_INT)
        # 下が範囲内の空マスなら現在マスの経路数を足す
        if h + 1 < H and grid[h + 1][w] == ".":
            dp[h + 1][w] += dp[h][w]
            # modを取って更新
            dp[h + 1][w] = np.mod(dp[h + 1][w], MOD_INT)

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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

MOD = pow(10, 9) + 7

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

@lru_cache(maxsize=H*W)
def calc(h, w):
    if h == H -1 and w == W -1:
        return 1
    count = 0
    # right
    if w + 1 < W  and A[h][w + 1] == ".":
        count += calc(h, w + 1)
        count %= MOD

    if h + 1 < H  and A[h + 1][w] == ".":
        count += calc(h + 1, w)
        count %= MOD

    return count % MOD

for w in reversed(range(W)):
    for h in reversed(range(H)):
        calc(h, w)
print(calc(0,0))

Submission status: Time Limit Exceeded

Solution code:
from itertools import *
import sys
import numpy as np
md=10**9+7
mis=map(int,sys.stdin.readline().split())

h,w=mis
t=np.zeros((h+1,w+1),dtype="uint64")
t[1][1]=1
s=[]
for _ in range(h):
    s+=[input()]

for i,j in product(range(h),range(w)):
    if i==0 and j==0:continue
    if s[i][j]==".":
        t[i+1][j+1]=(t[i][j+1]+t[i+1][j])%md
    else:
        t[i+1][j+1]=0

print(t[-1][-1])

Submission status: Time Limit Exceeded

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

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
    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():  # Grid 1
    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]


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

Submission status: Time Limit Exceeded

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():  # Grid 1
    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]


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

Submission status: Time Limit Exceeded

Solution code:
import collections

H,W = map(int,input().split())
L = [input() for i in range(H)]

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

cnt_list = [[float("inf") for x in range(W)] for y in range(H)]
cnt_list[0][0] = 1

q = collections.deque([(0,0)])

while q :
    y,x = q.popleft()
    for dy,dx in dxy :
        ny = y + dy
        nx = x + dx
        
        if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
            continue
        if L[ny][nx] == "#" :
            continue
        if cnt_list[ny][nx] < float("inf") :
            cnt_list[ny][nx] += cnt_list[y][x]
        else :
            cnt_list[ny][nx] = cnt_list[y][x]
            q.append((ny,nx))
ans = cnt_list[-1][-1]
if ans < float("inf") :
    ans %= 10**9+7
else :
    ans = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
(H,W) = map(int,input().split())
#A = [ list(input()) for _ in range(H) ]
A = np.zeros((H+2,W+2),dtype=np.int)

for y in range(1,H+1):
    line = list(input())
    for x in range(1,W+1):
        if line[x-1] == '.':
            A[y,x] = 1

#dic = {'.':1, '#':0}
#A = list(map(lambda a: list(map(lambda c: dic[c], a)),A))
#A = np.array(A,dtype=np.int)

M = 10**9 + 7

N = np.zeros((H+2,W+2),dtype=np.int64)
N[H+1,W] = 1
for y in range(H,0,-1):
    for x in range(W,0,-1):
        if A[y,x] == 1:
            N[y,x] = (N[y,x+1] + N[y+1,x]) % M

#print(A)
#print(N)
print(N[1,1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
(H,W) = map(int,input().split())
A = [ list(input()) for _ in range(H) ]

for i in range(H):
    A[i].append('#')
    A[i].insert(0,'#')
A.append(['#']*(W+2))
A.insert(0,['#']*(W+2))

dic = {'.':1, '#':0}
A = list(map(lambda a: list(map(lambda c: dic[c], a)),A))
A = np.array(A,dtype=np.int)

M = 10**9 + 7

N = np.zeros((H+2,W+2),dtype=np.int64)
N[H+1,W] = 1
for y in range(H,0,-1):
    for x in range(W,0,-1):
        if A[y,x] == 1:
            N[y,x] = (N[y,x+1] + N[y+1,x]) % M

print(N[1,1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
(H,W) = map(int,input().split())
A = [ list(input()) for _ in range(H) ]

for i in range(H):
    A[i].append('#')
    A[i].insert(0,'#')
A.append(['#']*(W+2))
A.insert(0,['#']*(W+2))

M = 10**9 + 7

N = np.zeros((H+2,W+2),dtype=np.int64)
N[H+1,W] = 1
for y in range(H,0,-1):
    for x in range(W,0,-1):
        if A[y][x] == '.':
            N[y,x] = (N[y,x+1] + N[y+1,x]) % M

print(N[1,1])

Submission status: Time Limit Exceeded

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


H, W = map(int, input().split())
graph = [dict() for _ in range(H * W)]
s_list = []
for i in range(H):
    s = list(input())
    s_list.append(s)

for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            continue
        if i + 1 < H and s_list[i + 1][j] == ".":
            graph[i * W + j][(i + 1) * W + j] = 1

        if j + 1 < W and s_list[i][j + 1] == ".":
            graph[i * W + j][i * W + j + 1] = 1

dijkstra = Dijkstra(graph, 0)
_, dijkstra_result = dijkstra.execute()

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

Submission status: Accepted

Solution code:
from collections import*
mod=10**9+7
h,w=map(int,input().split())
a=[input() for _ in range(h)]
dx=[0,1]
dy=[1,0]
d=[[0]*w for _ in range(h)]
v=[[0]*w for _ in range(h)]
d[0][0]=1
q=deque([(0,0)])
while q:
  x,y=q.popleft()
  if v[x][y]:continue
  v[x][y]=1
  for i,j in zip(dx,dy):
    nx=x+i
    ny=y+j
    if 0<=nx<h and 0<=ny<w and a[nx][ny]==".":
      d[nx][ny]+=d[x][y]
      d[nx][ny]%=mod
      q.append((nx,ny))
print(d[-1][-1])

Submission status: Accepted

Solution code:
mod = 10**9+7
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
dp = [[0]*W for _ in range(H)]
dp[0][0]=1

for i in range(H):
    for j in range(W):
        if i+1<H and maze[i+1][j]==".":
            dp[i+1][j] += dp[i][j]%mod
        if j+1<W and maze[i][j+1]==".":
            dp[i][j+1] += dp[i][j]%mod
            
print(dp[H-1][W-1]%mod)

Submission status: Accepted

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

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

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

for y in range(h):
    for x in range(w):
        if grid[y][x] == ".":
            if y > 0:
                dp[y][x] += dp[y-1][x]
            if x > 0:
                dp[y][x] += dp[y][x-1]

            dp[y][x] %= m

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

Submission status: Accepted

Solution code:

H, W = map(int, input().split())
grid = []
d = [(1, 0), (0, 1)]
for _ in range(H):
    grid.append(input())
dp = [[0 for _ in range(W)] for _ in range(H)]
mod = 1e9 + 7
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        if h > 0 and grid[h - 1][w] == '.':
            dp[h][w] = (dp[h][w] + dp[h - 1][w]) % mod
        if w > 0 and grid[h][w - 1] == '.':
            dp[h][w] = (dp[h][w] + dp[h][w - 1]) % mod
print(int(dp[H - 1][W - 1]))

Submission status: Accepted

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

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

MOD = 10**9 + 7

dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
dire = [[1,0], [0,1]] #下　右

for i in range(H):
    for j in range(W):
        if A_map[i][j] == '#':
            continue
        for k in dire:
            if 0 <= i+k[0] <= H-1 and  0 <= j+k[1] <= W-1:
                if A_map[i+k[0]][j+k[1]] == '.':
                    dp[i+k[0]][j+k[1]] +=  dp[i][j]%MOD
                    dp[i+k[0]][j+k[1]] %= MOD
#print(dp)
print(dp[H-1][W-1]%MOD)

Submission status: Accepted

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

def main():
    mod = 10**9 + 7
    h, w = map(int, input().split())

    dp = [0] * (w + 1)
    dp[1] = 1
    for _ in range(h):
        a = input()
        for i in range(w):
            if a[i] == '#':
                dp[i+1] = 0
            else:
                dp[i+1] += dp[i]
                dp[i+1] %= mod

    print(dp[w])

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

#import
#import math
#import numpy as np
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

def mod(num):
    return num % (10 ** 9 + 7)
    
dp = [[0] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            dp[i][j] = 1
            continue

        if A[i][j] == "#":
            continue

        if i == 0:
            dp[i][j] = dp[i][j - 1]
        elif j == 0:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = mod(dp[i - 1][j] + dp[i][j - 1])
            
print(dp[-1][-1])

Submission status: Accepted

Solution code:
''' ===============================
	-- @uthor : Kaleab Asfaw
	-- Handle : kaleabasfaw2010
	-- Bio    : High-School Student
	==============================='''

# Fast IO
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
	newlines = 0
	def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b: break
			ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0; return self.buffer.read()
	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines -= 1; return self.buffer.readline()
	def flush(self):
		if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
	def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")
# Others
# from math import floor, ceil, gcd
# from decimal import Decimal as d
mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
	ans = 1
	for i in range(1, x+1): ans = (ans * i) % mod
	return ans
def arr2D(n, m, default=0):
	lst = []
	for i in range(n): temp = [default] * m; lst.append(temp)
	return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def solve(n, m, grid):
	dp = arr2D(n, m)
	dp[0][0] = 1
	for i in range(n):
		for j in range(m):
			if grid[i][j] == "." and ((i > 0 and grid[i-1][j] == ".") or (j > 0 and grid[i][j-1] == ".")):
				dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % mod
	return dp[n-1][m-1]

n, m = list(map(int, input().split()))
grid = []
for i in range(n):
	grid.append(input())
print(solve(n, m, grid))

Submission status: Accepted

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

def main(h,w,a):
    mod = 10**9 + 7
    dp = [[0 for i 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 i==1 and j==1:
                continue
            if a[i-1][j-1]=="#":
                continue
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod
    print(dp[h][w])

if __name__=="__main__":
    h,w,a = getval()
    main(h,w,a)

Submission status: Accepted

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

def main(h,w,a):
    mod = 10**9 + 7
    dp = [[0 for i 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 i==1 and j==1:
                continue
            if a[i-1][j-1]=="#":
                continue
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod
    print(dp[h][w])

if __name__=="__main__":
    h,w,a = getval()
    main(h,w,a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    H,W =map(int,input().split())
    A =[]
    mod =10**9+7
    for i in range(H):
        a =list(input())
        A.append(a)

    dp =[[0] *W for _ in range(H)]
    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]
                dp[i+1][j] %=mod

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





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
H, W = map(int, input().split())
maze = []
for _ in range(H):
  maze.append(input())

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

for i in range(H):
  for j in range(W):
    if i-1 >= 0 and maze[i][j] == ".":
      dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD
    if j-1 >= 0 and maze[i][j] == ".":
      dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)
import itertools as it
import collections as cl
from collections import deque
import math
from functools import reduce
from collections import defaultdict
MOD = 10 ** 9 + 7

def li():
    return [int(x) for x in input().split()]


# dp[y][x]: (x, y)マスに行く経路の数

H, W = li()
maze = [list(input()) for _ in range(H)]
dp = [[0] * W for _ in range(H)]

dp[0][0] = 1

for y in range(H):
    for x in range(W):
        if maze[y][x] == '#':
            continue
        if y > 0:
            dp[y][x] += dp[y-1][x]
        if x > 0:
            dp[y][x] += dp[y][x-1]
        dp[y][x] %= MOD

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