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:
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll MOD = 1e9 + 7;
ll INF = 1e18;
vector<vector<int>> vec;
vector<vector<int>> dp;
int h, w;
void rec(int y, int x)
{
    if (vec[y][x] == '#')
        return; //壁だったら考えるまでもないです
    if (y >= 1)
    {
        if (vec[y][x] == '.')
        {
            dp[y][x] += dp[y - 1][x];
            dp[y][x] %= MOD;
        }
    }
    if (x >= 1)
    {
        if (vec[y][x] == '.')
        {
            dp[y][x] += dp[y][x - 1];
            dp[y][x] %= MOD;
        }
    }
}
int main()
{
    cin >> h >> w;
    vec.resize(h, vector<int>(w));
    dp.resize(h, vector<int>(w));
    for (int i = 0; i < h; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < w; j++)
        {
            vec[i][j] = s[j];
        }
    }
    dp[0][0] = 1;
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            rec(i, j);
        }
    }
    cout << dp[h - 1][w - 1] % MOD << endl;
}

Submission status: Runtime Error

Solution code:
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll MOD = 1e9 + 7;
ll INF = 1e18;
vector<vector<int>> vec;
vector<vector<int>> dp;
int h, w;
void rec(int y, int x)
{
    if (vec[y][x] == '#')
        return; //壁だったら考えるまでもないです
    if (y >= 1)
    {
        if (vec[y + 1][x] == '.')
        {
            dp[y][x] += dp[y - 1][x];
            dp[y][x] %= MOD;
        }
    }
    if (x >= 1)
    {
        if (vec[y][x] == '.')
        {
            dp[y][x] += dp[y][x - 1];
            dp[y][x] %= MOD;
        }
    }
}
int main()
{
    cin >> h >> w;
    vec.resize(h, vector<int>(w));
    dp.resize(h, vector<int>(w));
    for (int i = 0; i < h; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < w; j++)
        {
            vec[i][j] = s[j];
        }
    }
    dp[0][0] = 1;
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            rec(i, j);
        }
    }
    cout << dp[h - 1][w - 1] % MOD << endl;
}

Submission status: Runtime Error

Solution code:
MOD = 10**9+7

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

dp = [[-1]*W for _ in range(H)]
def rec(h, w):
    if dp[h][w]!=-1:
        return dp[h][w]
    else:
        dp[h][w] = 0
        if h<H-1:
            if a[h+1][w]!='#':
                dp[h][w] = rec(h+1, w)%MOD
        if w<W-1:
            if a[h][w+1]!='#':
                dp[h][w] += rec(h, w+1)%MOD
        if h==H-1 and w==W-1:
            dp[h][w] = 1
        return dp[h][w]%MOD

print(rec(0,0))

Submission status: Runtime Error

Solution code:
def bfs(h,w):
    if l[h][w]!=".":
        return 
    if h+1<H:
        if l[h+1][w]=="." and h+1<H:
            dp[h+1][w]+=dp[h][w]
            dp[h+1][w]%=(10**9+7)
            que.append([h+1,w])
    if w+1<W:
        if l[h][w+1]==".":
            dp[h][w+1]+=dp[w][h]
            dp[h][w+1]%=(10**9+7)
            que.append([h,w+1])
    l[h][w]="!"
    return

H,W=map(int,input().split())
l=[]
dp=[[0]*W for i in range(H)]

for _ in range(H):
    l.append(list(input()))

que=[[0,0]]
dp[0][0]=1
while True:
    
    if len(que)==0:
        break
    temp=que.pop(0)
    bfs(temp[0],temp[1])
    """
    for item in dp:
        print(item)
    print(temp)
    print("===================================")
    """
#print(l)
#print(dp)
print(dp[-1][-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
h, w = list(map(int, input().split()))
data = []
for i in range(h):
    data.append(list(input()))
dp = [[-1 for i in range(w)] for j in range(h)]
dp[0][0] = 1
def cal(row, column):
    if row < 0 or column < 0:
        return 0

    if data[row][column] == '#':
        return 0

    if dp[row][column] == -1:
        dp[row][column]  = cal(row - 1, column) + cal(row, column - 1)


    return dp[row][column]
mod = (10 ** 9) + 7
print(cal(h - 1, w - 1) % mod)

Submission status: Runtime Error

Solution code:
h, w = list(map(int, input().split()))
data = []
for i in range(h):
    data.append(list(input()))
dp = [[None for i in range(w)] for j in range(h)]
dp[0][0] = 1
def cal(row, column):
    if row < 0 or column < 0:
        return 0

    if data[row][column] == '#':
        return 0

    if dp[row][column] == None:
        dp[row][column]  = cal(row - 1, column) + cal(row, column - 1)


    return dp[row][column]
mod = (10 ** 9) + 7
print(cal(h - 1, w - 1) % mod)

Submission status: Runtime Error

Solution code:
h, w = list(map(int, input().split()))
data = []
for i in range(h):
    data.append(list(input()))
dp = [[None for i in range(w)] for j in range(h)]
dp[0][0] = 1
def cal(row, column):
    if row < 0 or column < 0:
        return 0

    if data[row][column] == '#':
        return 0

    if dp[row][column] == None:
        dp[row][column]  = cal(row - 1, column) + cal(row, column - 1)
        return dp[row][column]
    else:

        return dp[row][column]
mod = (10 ** 9) +7
print(cal(h - 1, w - 1) % mod)

Submission status: Runtime Error

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


const int MOD = 1e9 + 7;
int dp[1<<10][1<<10];

char s[1<<10][1<<10];
 



int main () {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int n, m; 
  cin >> n >> m;
  for (int i = 0; i < n; ++i) cin >> s[i];
  dp[0][0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) if ((i != 0 or j != 0) and s[i][j] == '.') {
      (dp[i][j] = (j ? dp[i][j - 1] : 0) + (i ? dp[i - 1][j] : 0)) %= MOD;
    }
  }
  cout << dp[n - 1][m - 1] << '\n';
}

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
M = [input() for i in range(H)]
dp = [[0 for i in range(W)] for j in range(H)]
dp[0][0] = 1

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

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
h, w = [int(i) for i in sys.stdin.readline().split()]
MAP = []
memo_ls = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    inp = [0 if i == "." else 1 for i in input()]
    MAP.append(inp)


memo_ls[h-1][w-1] = 1
for _h in range(h-1,-1,-1):
    for _w in range(w-1,-1,-1):
        if MAP[_h][_w] == 1:
            continue
        if _w < w - 1:
            memo_ls[_h][_w] += memo_ls[_h][_w+1]
        if _h < h - 1:
            memo_ls[_h][_w] += memo_ls[_h+1][_w]
print(int(memo_ls[0][0] % (1e9+7)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
h, w = [int(i) for i in sys.stdin.readline().split()]
MAP = []
memo_ls = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    inp = [0 if i == "." else 1 for i in sys.stdin.readline()][:-1]
    MAP.append(inp)


memo_ls[h-1][w-1] = 1
for _h in range(h-1,-1,-1):
    for _w in range(w-1,-1,-1):
        if MAP[_h][_w] == 1:
            continue
        if _w < w - 1:
            memo_ls[_h][_w] += memo_ls[_h][_w+1]
        if _h < h - 1:
            memo_ls[_h][_w] += memo_ls[_h+1][_w]
print(int(memo_ls[0][0] % (1e9+7)))

Submission status: Runtime Error

Solution code:
import sys
h, w = [int(i) for i in sys.stdin.readline().split()]
MAP = []
memo_ls = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    inp = [0 if i == "." else 1 for i in sys.stdin.readline()][:-1]
    MAP.append(inp)


memo_ls[h-1][w-1] = 1
for _h in range(h-1,-1,-1):
    for _w in range(w-1,-1,-1):
        if MAP[_h][_w] == 1:
            continue
        if _w < w - 1:
            memo_ls[_h][_w] += memo_ls[_h][_w+1]
        if _h < h - 1:
            memo_ls[_h][_w] += memo_ls[_h+1][_w]
print(int(memo_ls[0][0] % (1e9+7)))

Submission status: Runtime Error

Solution code:
import sys
import math

class Solution(object):
	def __init__(self):
		self.h = 0
		self.w = 0
		self.matrix = None

	def readInput(self):
		a = sys.stdin.readline().split()
		self.h = int(a[0])
		self.w = int(a[1])
	
		self.matrix = [['.'] * self.w for i in xrange(self.h)]
		for r in xrange(self.h):		
			a = sys.stdin.readline()
			for c in xrange(self.w):
				self.matrix[r][c] = a[c]

	def numPaths(self):
		dp = [[0] * self.w for i in xrange(self.h)]
		dp[0][0] = 1
		for r in xrange(self.h):
			for c in xrange(self.w):
				if self.matrix[r][c] == '#':
					dp[r][c] = 0
					continue
				if r == 0 and c == 0:
					continue
			
				if r == 0:
					dp[r][c] = dp[r][c-1]
				elif c == 0:
 					dp[r][c] = dp[r-1][c]
				else:
					dp[r][c] = dp[r-1][c] + dp[r][c-1]

		print int(dp[self.h-1][self.w-1] % (math.pow(10,9) + 7))


if __name__ == '__main__':
	s = Solution()
	s.readInput()
	s.numPaths()

Submission status: Runtime Error

Solution code:
import sys
import math

class Solution(object):
	def __init__(self):
		self.h = 0
		self.w = 0
		self.matrix = None

	def readInput(self):
		a = sys.stdin.readline().split()
		self.h = int(a[0])
		self.w = int(a[1])
	
		self.matrix = [['.'] * self.w for i in xrange(self.h)]
		for r in xrange(self.h):		
			a = sys.stdin.readline()
			for c in xrange(self.w):
				self.matrix[r][c] = a[c]

	def numPaths(self):
		dp = [[0] * self.w for i in xrange(self.h)]
		dp[0][0] = 1
		for r in xrange(self.h):
			for c in xrange(self.w):
				if self.matrix[r][c] == '#':
					dp[r][c] = 0
					continue
				if r == 0 and c == 0:
					continue
			
				if r == 0:
					dp[r][c] = dp[r][c-1]
				elif c == 0:
 					dp[r][c] = dp[r-1][c]
				else:
					dp[r][c] = dp[r-1][c] + dp[r][c-1]

		print dp[self.h-1][self.w-1] % (math.pow(10,9) + 7)


if __name__ == '__main__':
	s = Solution()
	s.readInput()
	s.numPaths()

Submission status: Runtime Error

Solution code:
divisor = 10 ** 9 + 7
h, w, n = map(int, input().split())
a = [['.'] * w for _ in range(h)]
for _ in range(n):
  r, c = map(int, input().split())
  a[r - 1][c - 1] = '#'
for i in range(h):
  a[i] = ''.join(a[i])
dp = [[0] * w for _ in range(h)]
dp[0][0] = 1
dp0 = dp[0]
a0 = a[0]
for j in range(1, w):
  if a0[j] != '#':
    dp0[j] = dp0[j - 1]
for i in range(1, h):
  dpi = dp[i]
  dpi1 = dp[i - 1]
  ai = a[i]
  if ai[0] != '#':
    dpi[0] = dpi1[0]
  for j in range(1, w):
    if ai[j] != '#':
      dpi[j] = (dpi1[j] + dpi[j - 1]) % divisor
print(dp[h - 1][w - 1])

Submission status: Runtime Error

Solution code:
def main():
  divisor = 10 * 9 + 7
  h, w = map(int, input().split())
  a = [input() for _ in range(h)]
  dp = [[0] * w for _ in range(h)]
  dp[0][0] = 1
  for i in range(h):
    ai = a[i]
    ai1 = a[i + 1]
    dpi = dp[i]
    dpi1 = dp[i + 1]
    for j in range(w):
      if i + 1 < h and ai1[j] != '#':
        dpi1[j] = (dpi1[j] + dpi[j]) % divisor
      if j + 1 < w and ai[j + 1] != '#':
        dpi[j + 1] = (dpi[j + 1] + dpi[j]) % divisor
  print(dp[h - 1][w - 1])
main()

Submission status: Runtime Error

Solution code:
def paths(i, j):

    if i == h - 1 and j == w - 1:
        return 1
    if a[i][0][j] == '#':
        return 0
    if i < h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j) + paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i == h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i < h - 1 and j == w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j)
            return dp[i][j]
        else:
            return dp[i][j]


h, w = map(int, input().split())
a = [[] for _ in range(h)]
m = 1000000007
for i in range(h):
    a[i].append(input())
dp = [[-1 for _ in range(1000)] for _ in range(1000)]
print(paths(0, 0) % m)

Submission status: Runtime Error

Solution code:
def valid(i,j):
    if i>=0 and i<h and j>=0 and j<w:
        return 1
    return 0
def paths(i,j):
 
    if valid(i,j)==0 or a[i][0][j]=='#':
        return 0
    if i==h-1 and j==w-1:
        return 1

    if dp[i][j]==-1:
           a1=0
           a1+=paths(i+1,j)%m
           a1+=paths(i,j+1)%m
           dp[i][j]=a1%m
           return dp[i][j]
    else:
            return dp[i][j]



h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(1000)]for _ in range(1000)]
print(paths(0,0))

Submission status: Runtime Error

Solution code:
def valid(i,j):
    if i>=0 and i<h and j>=0 and j<w:
        return 1
    return 0
def paths(i,j):

    if valid(i,j)==0 or  a[i][0][j]=='#':
        return 0
    if i==h-1 and j==w-1:
        return 1

    if dp[i][j]==-1:
           a=0
           a+=paths(i+1,j)%m
           a+=paths(i,j+1)%m
           dp[i][j]=a%m
           return dp[i][j]
    else:
            return dp[i][j]



h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(1000)]for _ in range(1000)]
print(paths(0,0))

Submission status: Runtime Error

Solution code:
def valid(i,j):
    if i>=0 and i<h and j>=0 and j<w:
        return 1
    return 0
def paths(i,j):

    if valid(i,j)==0 or  a[i][0][j]=='#':
        return 0
    if i==h-1 and j==w-1:
        return 1

    if dp[i][j]==-1:
           dp[i][j]=(paths(i+1,j)%m+paths(i,j+1)%m)%m
           return dp[i][j]
    else:
            return dp[i][j]



h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(1000)]for _ in range(1000)]
print(paths(0,0))

Submission status: Runtime Error

Solution code:
def valid(i,j):
    if i>=0 and i<h and j>=0 and j<w:
        return 1
    return 0
def paths(i,j):

    if valid(i,j)==0 or  a[i][0][j]=='#':
        return 0
    if i==h-1 and j==w-1:
        return 1

    if dp[i][j]==-1:
           dp[i][j]=(paths(i+1,j)%m+paths(i,j+1)%m)%m
           return dp[i][j]
    else:
            return dp[i][j]



h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(w+1)]for _ in range(h+1)]
print(paths(0,0))

Submission status: Runtime Error

Solution code:
def valid(i,j):
    if i>=0 and i<h and j>=0 and j<w:
        return 1
    return 0
def paths(i,j):

    if valid(i,j)==0 or  a[i][0][j]=='#':
        return 0
    if i==h-1 and j==w-1:
        return 1

    if dp[i][j]==-1:
           dp[i][j]=(paths(i+1,j)%m+paths(i,j+1)%m)%m
           return dp[i][j]
    else:
            return dp[i][j]



h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(w)]for _ in range(h)]
print(paths(0,0))

Submission status: Runtime Error

Solution code:
def valid(i,j):
    if i>=0 and i<h and j>=0 and j<w:
        return 1
    return 0
def paths(i,j):
 
    if valid(i,j)==0 or  a[i][0][j]=='#':
        return 0
    if i==h-1 and j==w-1:
        return 1

    if dp[i][j]==-1:
           dp[i][j]=paths(i+1,j)+paths(i,j+1)
           return dp[i][j]
    else:
            return dp[i][j]



h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(w)]for _ in range(h)]
print(paths(0,0)%m)

Submission status: Runtime Error

Solution code:
def valid(i,j):
    if i>=0 and i<h and j>=0 and j<w:
        return 1
    return 0
def paths(i,j):

    if a[i][0][j]=='#' or valid(i,j)==0:
        return 0
    if i==h-1 and j==w-1:
        return 1
    
    if dp[i][j]==-1:
           dp[i][j]=paths(i+1,j)+paths(i,j+1)
           return dp[i][j]
        else:
            return dp[i][j]
   


h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(w+1)]for _ in range(h+1)]
print(paths(0,0)%m)

Submission status: Runtime Error

Solution code:
def valid(i,j):
    if i>=0 and i<h and j>=0 and j<w:
        return 1
    return 0
def paths(i,j):

    if a[i][0][j]=='#' or valid(i,j)==0:
        return 0
    if i==h-1 and j==w-1:
        return 1
    if i<h-1 and j<w-1:
        if dp[i][j]==-1:
          dp[i][j]=paths(i+1,j)+paths(i,j+1)
          return dp[i][j]
        else:
            return dp[i][j]
    if i==h-1 and j<w-1:
        if dp[i][j]==-1:
            dp[i][j]=paths(i,j+1)
            return dp[i][j]
        else:
            return dp[i][j]
    if i<h-1 and j==w-1:
        if dp[i][j]==-1:
            dp[i][j]=paths(i+1,j)
            return dp[i][j]
        else:
            return dp[i][j]


h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(w+1)]for _ in range(h+1)]
print(paths(0,0)%m)

Submission status: Runtime Error

Solution code:
def valid(i,j):
    if i>=0 and i<h and j>=0 and j<w:
        return 1
    return 0
def paths(i,j):

    if a[i][0][j]=='#' or valid(i,j)==0:
        return 0
    if i==h-1 and j==w-1:
        return 1
    if i<h-1 and j<w-1:
        if dp[i][j]==-1:
          dp[i][j]=paths(i+1,j)+paths(i,j+1)
          return dp[i][j]
        else:
            return dp[i][j]
    if i==h-1 and j<w-1:
        if dp[i][j]==-1:
           dp[i][j]=paths(i,j+1)
           return dp[i][j]
        else:
            return dp[i][j]
    if i<h-1 and j==w-1:
        if dp[i][j]==-1:
           dp[i][j]=paths(i+1,j)
           return dp[i][j]
        else:
            return dp[i][j]


h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(w)]for _ in range(h)]
print(paths(0,0)%m)

Submission status: Runtime Error

Solution code:
def valid(i,j):
    if i>=0 and i<h and j>=0 and j<w:
        return 1
    return 0
def paths(i,j):

    if a[i][0][j]=='#' or valid(i,j)==0:
        return 0
    if i==h-1 or j==w-1:
        return 1
    else:
        if dp[i][j]==-1:
          dp[i][j]=paths(i+1,j)+paths(i,j+1)
          return dp[i][j]
        else:
            return dp[i][j]
    '''elif i==h-1 and j<w-1:
        if dp[i][j]==-1:
           dp[i][j]=paths(i,j+1)
           return dp[i][j]
        else:
            return dp[i][j]
    elif i<h-1 and j==w-1:
        if dp[i][j]==-1:
           dp[i][j]=paths(i+1,j)
           return dp[i][j]
        else:
            return dp[i][j]'''


h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(w)]for _ in range(h)]
print(paths(0,0)%m)

Submission status: Runtime Error

Solution code:
def valid(i,j):
    if i>=0 and i<h and j>=0 and j<w:
        return 1
    return 0
def paths(i,j):

    if a[i][0][j]=='#' or valid(i,j)==0:
        return 0
    if i==h-1 and j==w-1:
        return 1
    else:
        if dp[i][j]==-1:
          dp[i][j]=(paths(i+1,j)+paths(i,j+1))%m
          return dp[i][j]
        else:
            return dp[i][j]
    '''elif i==h-1 and j<w-1:
        if dp[i][j]==-1:
           dp[i][j]=paths(i,j+1)
           return dp[i][j]
        else:
            return dp[i][j]
    elif i<h-1 and j==w-1:
        if dp[i][j]==-1:
           dp[i][j]=paths(i+1,j)
           return dp[i][j]
        else:
            return dp[i][j]'''


h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(w)]for _ in range(h)]
print(paths(0,0)%m)

Submission status: Runtime Error

Solution code:
def paths(i,j):

    if a[i][0][j]=='#':
        return 0
    if i==h-1 and j==w-1:
        return 1
    if i<h-1 and j<w-1:
        if dp[i][j]==-1:
          dp[i][j]=paths(i+1,j)+paths(i,j+1)
          return dp[i][j]
        else:
            return dp[i][j]
    elif i==h-1 and j<w-1:
        if dp[i][j]==-1:
           dp[i][j]=paths(i,j+1)
           return dp[i][j]
        else:
            return dp[i][j]
    elif i<h-1 and j==w-1:
        if dp[i][j]==-1:
           dp[i][j]=paths(i+1,j)
           return dp[i][j]
        else:
            return dp[i][j]


h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(w)]for _ in range(h)]
print(paths(0,0)%m)

Submission status: Runtime Error

Solution code:
def paths(i,j):

    if a[i][0][j]=='#':

        return 0
    if i==h-1 and j==w-1:
        return 1
    if i<h-1 and j<w-1:
        if dp[i][j]==-1:
          dp[i][j]=paths(i+1,j)+paths(i,j+1)
          return dp[i][j]
        else:
            return paths(i+1,j)+paths(i,j+1)
    elif i==h-1 and j<w-1:
        if dp[i][j]==-1:
           dp[i][j]=paths(i,j+1)
           return dp[i][j]
        else:
            return dp[i][j]
    elif i<h-1 and j==w-1:
        if dp[i][j]==-1:
           dp[i][j]=paths(i+1,j)
           return dp[i][j]
        else:
            return dp[i][j]


h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(w)]for _ in range(h)]
print(paths(0,0)%m)

Submission status: Runtime Error

Solution code:
import sys
from heapq import *
#from numpy import zeros
sys.setrecursionlimit(200000000000)
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: Runtime Error

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

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

dp = [[None] * w for _ in range(h)]
def dfs(hindex=h - 1, windex=w - 1):
    if field[hindex][windex] == "#":
        return 0
    if hindex == windex == 0:
        return 1

    if dp[hindex][windex] is not None:
        return dp[hindex][windex]
    r = (hindex and dfs(hindex - 1, windex)) + (windex and dfs(hindex, windex - 1))
    dp[hindex][windex] = r
    return r

print(dfs() % (10**9 + 7))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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

dp = [[0 for _ in range(h+1)] for _ in range(w+1)]
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]
            dp[i+1][j] %= mod
        if (j+1 < w) and (a[i][j+1] == '.'):
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= mod

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

Submission status: Runtime Error

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

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

dp = [[0 for _ in range(h+1)] for _ in range(w+1)]
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]
            dp[i+1][j] %= mod
        if (j+1 < w) and (a[i][j+1] == '.'):
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= mod

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

Submission status: Runtime Error

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

dp = [[0 for _ in range(h+1)] for _ in range(w+1)]
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]
            dp[i+1][j] %= mod
        if (j+1 < w) and (a[i][j+1] == '.'):
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= mod

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

Submission status: Runtime Error

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

dp = [[0 for _ in range(h+1)] for _ in range(w+1)]
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]
            dp[i+1][j] %= mod
        if j+1 < w and a[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= mod

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = []
for i in range(n):
    a.append(list(input()))
dp = [[0] * m for i in range(n)]
for i in range(n):
    for j in range(m):
        if i == 0 and j == 0 and a[i][j]!= '#':
            dp[i][j]+= 1
        elif i == 0 and a[i][j]!='#':
            dp[i][j]=dp[i][j-1]
        elif j == 0 and a[i][j]!='#':
            dp[i][j]=dp[i-1][j]
        elif a[i][j]!='#':
            dp[i][j]=dp[i-1][j]+dp[i][j-1]
print(int(dp[-1][-1]%(1e9+7)))

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
grid = [[c for c in input()] for r in range(H)]
paths = [[-1 for r in range(W)] for c in range(H)]
paths[0][0] = 1

def calc(r, c):
    if not ((0 <= r <= H-1) and (0 <= c <= W-1)): return 0
    if paths[r][c] == -1:
        if grid[r][c] == "#":
            paths[r][c] = 0
        else:
            paths[r][c] = (calc(r-1, c) + calc(r, c-1)) % (10**9+7)
    return paths[r][c]

print(calc(H-1, W-1))

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
grid = [[c for c in input()] for r in range(H)]
paths = [[-1 for r in range(W)] for c in range(H)]
paths[0][0] = 1

def calc(r, c):
    if not ((0 <= r <= H-1) and (0 <= c <= W-1)): return 0
    if paths[r][c] == -1:
        if grid[r][c] == "#":
            v = 0
        else:
            v = (calc(r-1, c) + calc(r, c-1)) % (10**9+7)
    paths[r][c] = v
    return paths[r][c]

print(calc(H-1, W-1))

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
grid = [[c for c in input()] for r in range(H)]
paths = [[0 for r in range(W)] for c in range(H)]

def calc(r, c):
    if not ((0 <= r <= H-1) and (0 <= c <= W-1)): return 0
    if r == 0 and c == 0: return 1
    if grid[r][c] == "#": return 0
    return (calc(r-1, c) + calc(r, c-1))

v = calc(H-1, W-1) % (10**9 + 7)
print(v)

Submission status: Runtime Error

Solution code:
height, width = (int(i) for i in input().split(" "))
print("{} height and {} width".format(height, width))

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

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

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

max_paths[0][0] = 1

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

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

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

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

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
dp = [[0]*(w+1) for i in range(h+1)]
a = list(input() for _ in range(h))
dp[0][0] = 1
#配るDP
for i in range(h):
    for j in range(w):
        if i+1 < h and a[i+1][j] ==".":
            dp[i+1][j] =(dp[i+1][j] + dp[i][j])%mod
        if j+1 < w and a[i][j+1] ==".":
            dp[i][j+1] = (dp[i][j+1]+dp[i][j])%mod
print(dp[h-1][w-1])