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: Runtime Error

Solution code:
import sys


def find_paths(mat, n, m):

    for i in range(n):

        if mat[i][0] != "#":
            dp[i][0] = 1

        else:
            break

    for j in range(m):

        if mat[0][j] != "#":
            dp[0][j] = 1

        else:
            break

    dp[0][0] = 0

    for i in range(1, n):
        for j in range(1, m):
            if mat[i][j] == "#":
                dp[i][j] = 0

            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    # print(dp)
    return int(dp[n - 1][m - 1] % (1e9+7))



n, m = list(map(int, sys.stdin.readline().split()))

mat = []
dp = [[0 for i in range(1001)] for j in range(1001)]

for i in range(n):
    mat.append([ch for ch in sys.stdin.readline().strip()])

# print(mat)
print(find_paths(mat, n, m))

Submission status: Runtime Error

Solution code:
import sys


def find_paths(mat, n, m, i, j, dp):

    if i == n - 1 and j == m - 1:
        return 1

    if i >= n or j >= m:
        return 0

    if mat[i][j] == "#":
        return 0

    if (i, j) in dp:
        return dp[(i, j)]

    dp[(i, j)] = int((find_paths(mat, n, m, i+1, j, dp) + find_paths(mat, n, m, i, j+1, dp)) % (1e9 + 7))
    return dp[(i, j)]



n, m = list(map(int, sys.stdin.readline().split()))

mat = []

for i in range(n):
    mat.append([ch for ch in sys.stdin.readline().strip()])


dp = {}
# print(mat)
print(find_paths(mat, n, m, 0, 0, dp))

Submission status: Runtime Error

Solution code:
import sys


def find_paths(mat, n, m):

    dp = [[0 for i in range(m)] for j in range(n)]

    for i in range(n):

        if mat[i][0] != "#":
            dp[i][0] = 1

        else:
            break

    for j in range(m):

        if mat[0][j] != "#":
            dp[0][j] = 1

        else:
            break

    dp[0][0] = 0


    for i in range(1, n):
        for j in range(1, m):
            if mat[i][j] == "#":
                dp[i][j] = 0

            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    # print(dp)
    return int(dp[n - 1][m - 1] % (1e9+7))



n, m = list(map(int, sys.stdin.readline().split()))

mat = []

for i in range(n):
    mat.append([ch for ch in sys.stdin.readline().strip()])


dp = {}
# print(mat)
print(find_paths(mat, n, m))

Submission status: Runtime Error

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: Runtime Error

Solution code:
h, w = map(int, input().split())
field = [input() for _ in range(h)]
MOD = 10 ** 9 + 7

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

for i in range(1, w):
    if field[0][i] == ".":
        dp[0][i] = dp[0][i-1] 

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

for row in range(1, h):
    for col in range(1, w):
        if field[i][j] == ".":
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
import sys
import os
f = open('input.txt', 'r')
sys.stdin = f
m = 10**9+7
def nCr(n,r):
  if r*2>n:
      return nCr(n,n-r)
  else:
      a = b = 1
      for i in range(r):
          a = a * (n - i) % m
          b = b * (r - i) % m
      return (a * pow(b,m-2,m)) % m

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

grid=[]

for i in range(H):
    a= list(input())
    grid.append(a)

wall=[]
for i in range(H):
    for j in range(W):
        if grid[i][j]=="#":
            wall.append([i,j])

ans = nCr((H+W-2),(H-1))

for i in range(len(wall)):
    x = wall[i][0] + wall[i][1]
    y = (H-wall[i][0]) + (W-wall[i][1])
    ans -= nCr(x-1,wall[i][0]-1) * nCr(y-1,(H-wall[i][0])-1)

print(ans)

Submission status: Runtime Error

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

for i in range(H):
    line = list(input())
    map.append(line)
    dp.append([-1]*W)
#メモ化再帰
def dfs(h, w):#(h, w)までの経路の通りは何通りか?
    if dp[h][w]!=-1:
        return dp[h][w]
    if h==0 and w==0:
        return 1
    if h<0 or w<0 or h>=H or w>=W:
        return 0
    if map[h][w]=="#":
        return 0
    ans = dfs(h-1, w)+dfs(h, w-1)
    dp[h][w] = ans
    return ans
print(dfs(H-1, W-1)%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[input() for _ in range(h)]
mod=10**9+7
dp=[[0]*w for _ in range(w)]
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[-1][-1]%mod)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple

MODULO = pow(10, 9) + 7


def solve(values, h, w):
    dp = [[0] * (1 + w) for _ in range(1 + h)]
    dp[1][1] = 1
    # for i, row in enumerate(values):
    for i in range(h):
        # for j, v in enumerate(row):
        for j in range(w):
            if i + j != 0 and values[i][j] == ".":
                # if i + j != 0 and v == ".":
                LOG.debug((i, j, values[i][j]))
                # LOG.debug((i, j, v))
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j]) % MODULO
    LOG.debug("\n".join(map(str, dp)))
    return dp[h][w]


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    H, W = map(int, input().split())
    values = []
    for _ in range(H):
        values.append(input())
    result = solve(values, H, W)
    print(result)


def configure_log():
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple

MODULO = pow(10, 9) + 7


def solve(values: List[int], h: int, w: int) -> int:
    dp = [[0] * (1 + w) for _ in range(1 + h)]
    dp[1][1] = 1
    # for i, row in enumerate(values):
    for i in range(h):
        # for j, v in enumerate(row):
        for j in range(w):
            if i + j != 0 and values[i][j] == ".":
                # if i + j != 0 and v == ".":
                LOG.debug((i, j, values[i][j]))
                # LOG.debug((i, j, v))
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j]) % MODULO
    LOG.debug("\n".join(map(str, dp)))
    return dp[h][w]


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    H, W = map(int, input().split())
    values = []
    for _ in range(H):
        values.append(input())
    result = solve(values, H, W)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log(log_file: Optional[str] = None) -> None:
    "Configure the log output"
    log_formatter = logging.Formatter(
        "%(asctime)s - %(filename)s:%(lineno)d - " "%(levelname)s - %(message)s"
    )
    if log_file:
        handler = logging.FileHandler(filename=log_file)
    else:
        handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Runtime Error

Solution code:
20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................

Submission status: Runtime Error

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

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

mod = 10**9+7

for i in range(H):
  for j in range(W):
    dp[0][0] = 1
    if A[i][j] == "#":
      dp[i][j] = 0
    elif i == 0:
      dp[i][j] = dp[i][j-1]
    elif j == 0:
      dp[i][j] = dp[i-1][j]
    elif i != 0 and j != 0:
      dp[i][j] += (dp[i-1][j] + dp[i][j-1])%mod

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

Submission status: Runtime Error

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

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

mod = 10**9+7

for i in range(H):
  for j in range(W):
    dp[0][0] = 1
    if A[i][j] == "#":
      dp[i][j] = 0
    elif i == 0:
      dp[i][j] = dp[i][j-1]
    elif j == 0:
      dp[i][j] = dp[i-1][j]
    elif i != 0 and j != 0:
      dp[i][j] += (dp[i-1][j] + dp[i][j-1])%mod

print(dp[H][W])

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
#G=[[-1 if input() else 0 for i in range(W)] for _ in range(H)]

'''リストver
dp=[[-1]*W for _ in range(H)]
for i in range(H):
    s=input()
    for j in range(W):
        if s[j]=='#':
            dp[i][j]=0
dp[0][0]=1
'''

#numpy ver
import numpy as np
dp=np.array([list(input()) for _ in range(H)])

dp=np.where(dp=='.',-1,dp)
dp=np.where(dp=='#',0,dp)

dp=dp.astype(int)
dp[0][0]=1

for i in range(H):
    for j in range(W):
        if dp[i][j]==-1:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
            elif i>=1 and j==0:
                dp[i][j]=dp[i-1][j]
            elif i==0 and j>=1:
                dp[i][j]=dp[i][j-1]

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define ppi pair<int, int>
#define endl "\n"
#define nl cout << "\n"
#define deb(x) cout << #x << " " << x << endl;

const int N = 1010;
const int mod = 1e9 + 7;
int H, W;
char grid[N][N];

// dp[i][j] = #Ways to reach from (i, j) to (H, W)
int dp[N][N];

int Top_Down(int x = 1, int y = 1) {
    // Base Case
    if(x == H && y == W) return (dp[x][y] = 1);
    // Choice
    if(dp[x][y] != -1) return dp[x][y];
    int ways = 0;
    if(x <= H && grid[x+1][y] == '.') ways += Top_Down(x+1, y)%(mod);
    if(y <= W && grid[x][y+1] == '.') ways += Top_Down(x, y+1)%(mod);
    return (dp[x][y]=ways%(mod));
}

int32_t main() {
    IOS;
    memset(dp, -1, sizeof(dp));
    cin >> H >> W;
    for(int i = 1; i <= H; ++i) 
        for(int j = 1; j <= W; ++j) {
            cin >> grid[i][j];
        }
    //
    for(int i = 1; i <= H; ++i){
        for(int j = 1; j <= W; ++j)
            if((i == H and j == W) and grid[i][j]=='.') dp[i][j] = 1;
    }
    cout << Top_Down()%(mod) << endl;
    // for(int i = 1; i <= H; ++i){
    //     for(int j = 1; j <= W; ++j) cout << dp[i][j] << " ";
    //     cout << endl;
    // }
}

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
h, w = map(int, input().split())
a = [['#' for _ in range(w+2)]]
for _ in range(h):
	l = ['#']
	m = list(input())
	l += m
	l.append('#')
	a.append(l)
a.append(['#' for _ in range(w+2)])

dp1 = [[[False, False] for _ in range(w+2)] for _ in range(h+2)]

def dfs1(x, y):
	if a[x+1][y] == '.':
		dp1[x+1][y][0] = True
		dfs1(x+1, y)
	if a[x][y+1] == '.':
		dp1[x][y+1][1] = True
		dfs1(x, y+1)
	return

dp2 = [[0 for _ in range(w+2)] for _ in range(h+2)]
dp2[1][1] = 1
def dfs2(x, y):
	if dp1[x][y] == [False, False]:
		if a[x+1][y] == '.':
			dp2[x+1][y] += (dp2[x][y] % MOD)
			dp2[x+1][y] %= MOD
			dp1[x+1][y][0] = False
			dfs2(x+1, y)
		if a[x][y+1] == '.':
			dp2[x][y+1] += (dp2[x][y] % MOD)
			dp2[x][y+1] %= MOD
			dp1[x][y+1][1] = False
			dfs2(x, y+1)
	return

dfs1(1,1)
dfs2(1,1)
ans = dp2[h][w] % MOD
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(n):
  a.append(input())
ans=[0]*(n+1)
for i in range(n):
  for j in range(m):
    if a[i][j]==".":
      ans[j+1]+=ans[j]
    else :
      ans[j+1]=0
print(ans[m])

Submission status: Runtime Error

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

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
MOD = 10 ** 9 + 7
count = [0]
dp = [[-1] * W for _ in range(H)]

def dfs(x, y):
  ret = 0
  for nx, ny in ((1,0), (0,1)):
    nx += x
    ny += y
    if nx == W-1 and ny == H-1:
      ret += 1
    elif dp[ny][nx] > -1:
      ret += dp[ny][nx]
    elif nx < W and ny < H:
      if field[ny][nx] == "#":
        ret += dfs(nx, ny)
  dp[y][x] = ret % MOD
  return ret

dfs(0,0)
print(dp[0][0])

Submission status: Runtime Error

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

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
MOD = 10 ** 9 + 7
count = [0]
dp = [[-1] * W for _ in range(H)]

def dfs(x, y):
  ret = 0
  for nx, ny in ((1,0), (0,1)):
    nx += x
    ny += y
    if nx == W-1 and ny == H-1:
      ret += 1
    elif dp[ny][nx] > -1:
      ret += dp[ny][nx]
    elif nx < W and ny < H and field[ny][nx] == "#":
      ret += dfs(nx, ny)
  dp[y][x] = ret % MOD
  return ret

dfs(0,0)
print(dp[0][0])

Submission status: Runtime Error

Solution code:
import sys

EMPTY = '.'
WALL = "#"

MAX_VALUE = 1e9 + 7

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

if H == 0 or W == 0:
	print(0)
	sys.exit(0)

for i in range(H):
	grid.append(list(input()) + [WALL])
grid.append([WALL] * (W + 1))

dp = []
for row, r in enumerate(grid):
	dp.append([])

	for cell, value in enumerate(r):
		dp[row].append(0 if value == WALL else 1)
dp[-2][-2] = 0

for y in range(H):
	for x in range(W):
		if x == 0 and y == 0:
			continue

		if grid[y][x] == WALL:
			continue

		dp[y][x] = dp[y - 1][x] + dp[y][x - 1]
print(int(dp[-2][-2] % MAX_VALUE))

Submission status: Runtime Error

Solution code:
EMPTY = '.'
WALL = "#"

MAX_VALUE = 1e9 + 7

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

grid = []

for i in range(H):
	grid.append(list(input()) + [WALL])
grid.append([WALL] * (W + 1))

dp = []
for row, r in enumerate(grid):
	dp.append([])

	for cell, value in enumerate(r):
		dp[row].append(0 if value == WALL else 1)

dp[-2][-2] = 0

for y in range(H):
	for x in range(W):
		if x == 0 and y == 0:
			continue

		if grid[y][x] == WALL:
			continue

		dp[y][x] = dp[y - 1][x] + dp[y][x - 1]
print(int(dp[-2][-2] % MAX_VALUE))

Submission status: Runtime Error

Solution code:
EMPTY = '.'
WALL = "#"

MAX_VALUE = 10e9 + 7

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

grid = []

for i in range(H):
	grid.append(list(input()) + [WALL])
grid.append([WALL] * (W + 1))


def solve(paths, pos):
	x, y = pos
	if (x + 1 == H and y + 1 == W):
		return 1

	res = paths
	# Horizontally
	if (x < H) and grid[x + 1][y] != WALL:
		res += solve(paths, (x + 1, y))

	# Vertically
	if (y < W) and grid[x][y + 1] != WALL:
		res += solve(paths, (x, y + 1))
	return res


res = solve(0, (0, 0))
print(int(res % MAX_VALUE))

Submission status: Runtime Error

Solution code:
from math import inf

EMPTY = '.'
WALL = "#"

MAX_VALUE = 10e9 + 7

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

grid = []

for i in range(H):
	grid.append(list(input()) + [WALL])
grid.append([WALL] * (W + 1))


def solve(paths, pos):
	x, y = pos
	if (x + 1 == H and y + 1 == W):
		return 1

	res = paths
	# Horizontally
	if (x < H) and grid[x + 1][y] != WALL:
		res += solve(paths, (x + 1, y))

	# Vertically
	if (y < W) and grid[x][y + 1] != WALL:
		res += solve(paths, (x, y + 1))
	return res


res = solve(0, (0, 0))
print(int(res % MAX_VALUE))

Submission status: Runtime Error

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

count = [0]
def dfs(x, y):
  for nx, ny in ((1,0), (0,1)):
    nx += x
    ny += y
    if nx == W-1 and ny == H-1:
      count[0] += 1
      continue
    if nx >= W or ny >= H:
      continue
    if field[ny][nx] == "#":
      continue
    dfs(nx, ny)

dfs(0,0)
print(count[0])

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
l=[[0]*w]*h
m=[""]*h
for k in range(h):
  m[k]=input()
l[0][0]=1
for k in range(h):
  for j in range(w):
    if m[k][j]=="#":
      l[k][j]=0
    else:
      if k==0:
        if j!=0:
          l[k][j]=l[0][j-1]
      elif j==0:
        if k!=0:
          l[k][j]=l[k-1][j]
      else:
        l[k][j]=l[k-1][j]+l[k][j-1]
print(l[h][w]%1000000007)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
import copy

MOD = 10 ** 9 + 7
H, W = map(int, input().split())

a = [["#" for _ in range(W + 2)]]
for i in range(H):
    p = deque(list(input()))
    p.appendleft("#")
    p.append("#")
    a.append(list(p))
a.append(["#" for _ in range(W + 2)])

dp = [[0 for _ in range(H + 10)] for _ in range(W + 10)]
dp[0][1] = 1
for i in range(1, H + 1):
    for l in range(1, W + 1):
        if a[i][l] != "#":
            dp[i][l] = (dp[i][l - 1] + dp[i - 1][l]) % MOD
print(dp[H][W] % MOD)

Submission status: Runtime Error

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

# print(H, W) 
# print(grid)

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

for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            pass
        else:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]

print(dp[H][W])

Submission status: Runtime Error

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

dp = [[0 for _ in range(H+1)] for _ in range(W+1)]
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: Runtime Error

Solution code:
#include<iostream>
#include <vector>
using namespace std;

int main()
{    
    int H,W;
    cin >> H >> W;
    int A[H][W]={};
    for (int i = 0; i < H; ++i) {
        string s;   
        cin >> s;
        for (int j = 0; j < W; ++j) {
            if (s[j]=='#'){A[i][j]=1;}
        }
    }

    
    long long dp[H][W]={};


    dp[0][0]=0;
    if (A[1][0]==0){dp[1][0]=1;}
    if (A[0][1]==0){dp[0][1]=1;}


    for (int i = 2; i < H; ++i) {
        if (A[i][0]==0){dp[i][0]=dp[i-1][0];}
    }

    for (int i = 2; i < W; ++i) {
        if (A[0][i]==0){dp[0][i]=dp[0][i-1];}
    }

    

    for (int i = 1; i < H; ++i) {
        for (int j = 1; j < W; ++j) {
            //dp[i][j]=0;
            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][j-1]+dp[i-1][j];
            }
        }
    }

    long long ans;
    ans=dp[H-1][W-1]%1000000007;
    cout << ans << endl;
    return 0;

}

Submission status: Runtime Error

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

As = []
for _ in range(H):
  As.append(input())
paths = [[0 for _ in range(W)] for _ in range(H)]

paths[0][0] = 1

mod = 1e+9 + 7

for width in range(W):
  for height in range(H):
    if As[height][width] == "#":
      # 壁のマスであればスキップする
      continue
    if height < H-1:
      if As[height + 1][width] == ".":
        # 次のマスが通行可能であれば、これまでの経路を加える
        paths[height + 1][width] += paths[height][width]
    if width < W-1:
      if As[height][width + 1] == ".":
        # 次のマスが通行可能であれば、これまでの経路を加える
        paths[height][width + 1] += paths[height][width]

print(int(paths[H-1][W-1] % mod))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define lli long long
#define pb push_back
#define mp make_pair
using namespace std;
#define fin ios_base::sync_with_stdio(false); cin.tie(NULL);
int main(){
fin;
int h,w,i,j;
  cin>>h>>w;
  int dp[h][w];
  char m[h][w];
  int mod=1000000007;
  for(i=0;i<h;i++)
  {
    for(j=0;j<w;j++)
      cin>>m[i][j];
  }
  for(i=h-1;i>=0;i--)
  {
    for(j=w-1;j>=0;j--)
    {
      if(m[i][j]=='#')
        dp[i][j]=0;
      else if(i==h-1 && j==w-1)
        dp[i][j]=1;
      else if(i==h-1)
        dp[i][j]=dp[i][j+1];
      else if(j==w-1)
        dp[i][j]=dp[i+1][j];
      else
        dp[i][j]=(dp[i][j+1]+dp[i+1][j])%mod;
    }
  }
  cout<<dp[0][0]%mod;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define lli long long
#define pb push_back
#define mp make_pair
using namespace std;
#define fin ios_base::sync_with_stdio(false); cin.tie(NULL);
char m[1005][1005];
int main(){
fin;
int h,w,i,j;
  cin>>h>>w;
  int dp[h][w];
  for(i=0;i<h;i++)
  {
    for(j=0;j<w;j++)
      cin>>m[i][j];
  }
  for(i=h-1;i>=0;i--)
  {
    for(j=w-1;j>=0;j--)
    {
      if(m[i][j]=='#')
        dp[i][j]=0;
      else if(i==h-1 && j==w-1)
        dp[i][j]=1;
      else if(i==h-1)
        dp[i][j]=dp[i][j+1];
      else if(j==w-1)
        dp[i][j]=dp[i+1][j];
      else
        dp[i][j]=dp[i][j+1]+dp[i+1][j];
    }
  }
  cout<<dp[0][0];
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define lli long long
#define pb push_back
#define mp make_pair
using namespace std;
#define fin ios_base::sync_with_stdio(false); cin.tie(NULL);
char m[1005][1005];
int solve(int h,int w,int i,int j)
{
  if(m[i][j]=='#')
    return 0;
  if(i==h-1 && j==w-1)
    return 1;
  else if(i==h-1)
    return solve(h,w,i,j+1);
  else if(j==w-1)
    return solve(h,w,i+1,j);
  else
    return solve(h,w,i+1,j)+solve(h,w,i,j+1);
}
int main(){
fin;
int h,w,i,j;
  cin>>h>>w;
  for(i=0;i<h;i++)
  {
    for(j=0;j<w;j++)
      cin>>m[i][j];
  }
  cout<<solve(h,w,0,0);
}

Submission status: Runtime Error

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)])
grid[1][1] = 1
for y in range(1, a + 1):
    for x in range(1, b + 1):
        if grid[x][y] > 0:
            if grid[x + 1][y] != -1:
                grid[x + 1][y] += grid[x][y]
            if grid[x][y + 1] != -1:
                grid[x][y + 1] += grid[x][y]
print(grid[-2][-2])

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
grid=[None]*h
for i in range(h):
  grid[i]=input()
  
dp=[[0 for i in range(w)] for j in range(h)]
DIV=10**9+7
import deque
que=deque()
que.append([0,0,1])
while que:
  node=que.pop()
  y=node[0]
  x=node[1]
  p=node[2]
  dp[y][x]+=p
  dp[y][x]%=DIV
  if y+1<h and grid[y+1][x]!="#":
    que.append([y+1,x,dp[y][x]])
  if x+1<w and grid[y][x+1]!="#":
    que.append([y,x+1,dp[y][x+1]])
  
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
def main():
    MOD = int(1e9 + 7)
    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]

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

    for i in range(h):
        for j in range(w):
            if grid[i][j] != '#':
                if i > 0:
                    dp[i][j] += dp[i-1][j]

                if j > 0:
                    dp[i][j] += dp[i][j-1]

                if dp[i][j] > MOD:
                    dp[i][j] -= MOD

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



if __name__ == "__main__":
    main()