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:
# coding: utf-8
# Your code here!

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

field = []
for _ in range(H):
    temp_field = []
    for s in input():
        temp_field.append(0 if s == '.' else 1)
    field.append(temp_field)
    
dp = [[0] * (W + 1) for _ in range(H+1)]
dp[0][1] = 1

for h in range(1, H+1):
    for w in range(1, W+1):
        if field[h-1][w-1] == 0:
            dp[h][w] = dp[h-1][w] + dp[h][w-1]
            
#print(int(dp[-1][-1] % (1e9 + 7)))
print((dp[-1][-1] % (1_000_000_007)))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

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

field = []
for _ in range(H):
    temp_field = []
    for s in input():
        temp_field.append(0 if s == '.' else 1)
    field.append(temp_field)
    
dp = [[0] * (W + 1) for _ in range(H+1)]
dp[0][1] = 1

for h in range(1, H+1):
    for w in range(1, W+1):
        if field[h-1][w-1] == 0:
            dp[h][w] = dp[h-1][w] + dp[h][w-1]
            
print(int(dp[-1][-1] % (1e9 + 7)))

Submission status: Runtime Error

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

def main():
    #raw = ["3 4",
    #       "...#",
    #       ".#..",
    #       "...."]
    #H, W = map(int, raw[0].split())
    #mm = raw[1:]
    import sys
    H, W = map(int, sys.stdin.readline().split())
    mm = [sys.stdin.readline().split()[0] for _ in range(H)]

    MOD = 10 ** 9 + 7

    used = [[False] * W for _ in range(H)]
    memo = [[0] * W for _ in range(H)]

    def valid(x, y):
        return x >= 0 and x < H and y >= 0 and y < W and mm[x][y] == "."

    def dfs(x, y):
        if not valid(x, y):
            return 0
        if x == H - 1 and y == W - 1:
            return 1
        if used[x][y]:
            return memo[x][y]
        used[x][y] = True
        memo[x][y] += (dfs(x+1, y) % MOD + dfs(x, y+1) % MOD) % MOD
        return memo[x][y]

    print((dfs(0, 0) + MOD) % MOD)
    #for xs in memo:
    #    print(" ".join(map(str, xs)))

main()

Submission status: Runtime Error

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 range(W):
    for h in range(H):
        calc(h, w)
print(calc(0,0))

Submission status: Runtime Error

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


print(calc(0,0))

Submission status: Runtime Error

Solution code:
import numpy as np
h, w = map(int,input().split())
f = lambda:list(map(str,input().split()))
g = []
for i in range(h):
  li = f()
  g.append(li)
#print(g)
dp = np.zeros((h,w))
dp[0][0] = 1
#print(g[1][0] == '.')
#print(g[1][0])
#print(g[0][3])
mod = 10**9+7
for i in range(h):
  for j in range(w):
    if i+1<h and g[i+1][j] == '.':
      dp[i+1][j] = (dp[i+1][j] + dp[i][j])%mod
    if j+1<w and g[i][j+1] == '.':
      dp[i][j+1] = (dp[i][j+1] + dp[i][j])%mod
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
import numpy as np
h, w = map(int,input().split())
f = lambda:list(map(str,input().split()))
g = []
for i in range(h):
  li = f()
  g.append(li)
#print(g)
dp = np.zeros((h,w))
dp[0][0] = 1
#print(g[1][0] == '.')
#print(g[1][0])
#print(g[0][3])
for i in range(h):
  for j in range(w):
    if i+1<h and g[i+1][j] == '.':
      dp[i+1][j] = dp[i+1][j] + dp[i][j]
    if j+1<w and g[i][j+1] == '.':
      dp[i][j+1] =dp[i][j+1] + dp[i][j]
print(dp)
ans = int(dp[-1][-1])
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
import numpy as np
h, w = map(int,input().split())
f = lambda:list(map(str,input().split()))
g = []
for i in range(h):
  li = f()
  g.append(li)
#print(g)
dp = np.zeros((h,w))
#print(g[1][0] == '.')
#print(g[1][0])
#print(g[0][3])
for i in range(1,h):
  for j in range(1,w):
    if g[i-1][j] == '.' and g[i][j] != '#':
      if dp[i-1][j] == 0:
        dp[i][j] += 1
      else:
        dp[i][j] += dp[i-1][j]
    if g[i][j-1] == '.' and g[i][j] != '#':
      if dp[i][j-1] == 0:
        dp[i][j] += 1
      else:
        dp[i][j] += dp[i][j-1]
#print(dp)
ans = int(dp[-1][-1])
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using ull = unsigned long long;
//#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
template<class T> using V = vector<T>;
template<class T> using vv = vector<V<T>>;
template<class T> using VV = vector<V<T>>;
#define fi first
#define se second
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1);
const double EPS = 1e-10;
const ll MOD = 1e9+7;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
signed main(){
  int h,w;
  cin >> h >> w;
  vector<string> mp(h);
  REP(i,h) cin >> mp[i];
  vvl dp(h,vl(w,0));
  dp[0][0] = 1;
  REP(i,w){
    if(mp[0][i]=='#') break;
    dp[0][i] = 1;
  }
  REP(i,h){
    if(mp[i][0]=='#') break;
    dp[i][0] = 1;
  }
  REP(i,h-1){
    REP(j,w-1){
      if(mp[i+1][j+1]=='#') continue;
      dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j])%MOD;
    }
  }
  cout << dp[h-1][w-1] << endl;
}

Submission status: Runtime Error

Solution code:
h = int(input())
w = int(input())
grid = [int(i) for i in input().split()]
print("h", h)
print("w", w)
print("grid", grid)

Submission status: Runtime Error

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

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

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

for j in range(W):
  if a[0][i]==".":
    dp[0][i]=1

for i in range(1,H):
  for j in range(1,W):
    if a[i][j]==".":
      dp[i][j]=dp[i-1][j]+dp[i][j-1]

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

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
a=[]
dp={}
dp[(h-1,w-1)]=1
for i in range(h):
	a.append(list(input()))

def foo(i,j):
	if i>=h or j>=w:
		return 0
	if (i,j) in dp:
		return dp[(i,j)]
	ans=0
	if i+1<h and a[i+1][j]=='.':
		ans+=foo(i+1,j)
	if j+1<w and a[i][j+1]=='.':
		ans+=foo(i,j+1)
	dp[(i,j)]=ans%(1e9+7)
	return dp[(i,j)]

print(int(foo(0,0)))

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
grid = [["#"]*(W+2) for i in range(H+2)]
for i in range(H):
    s = input()
    for j in range(W):
        grid[i+1][j+1] = s[j]
ans = 0
def dfs(i = 1,j = 1):
    if (i,j) == (H,W):
        global ans
        ans += 1
        return
    if grid[i+1][j] == ".":
        dfs(i+1,j)
    if grid[i][j+1] == ".":
        dfs(i,j+1)
dfs()
ans %= 10**9 + 7   
print(ans)

Submission status: Runtime Error

Solution code:
import java.io.PrintWriter;
import java.util.*;


public class Main {
    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(System.out);
        Scanner sc = new Scanner(System.in);
        Task task = new Task();
        task.solve(sc, out);
        out.flush();
        sc.close();
    }

    static class Task {
        public void solve(Scanner sc, PrintWriter out) {
            int H = nint(sc);
            int W = nint(sc);
            List<Map<Integer, Integer>> graph = new ArrayList<>();
            List<String> sList = getStringList(sc, H);
            for (int i = 0; i <= H; i++) {
                for (int j = 0; j <= W; j++) {
                    Map<Integer, Integer> tmp = new HashMap<>();
                    graph.add(i*j, tmp);
                }
            }
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (sList.get(i).charAt(j) == '#') {
                        continue;
                    }
                    if (i + 1 < H && sList.get(i + 1).charAt(j) == '.') {
                        Map<Integer, Integer> tmp1 = graph.get(i * W + j);
                        tmp1.put((i + 1) * W + j, 1);
                        graph.set(i * W + j, tmp1);
                    }
                    if (j + 1 < W && sList.get(i).charAt(j + 1) == '.') {
                        Map<Integer, Integer> tmp2 = graph.get(i * W + j);
                        tmp2.put(i * W + j + 1, 1);
                        graph.set(i * W + j, tmp2);

                    }
                }
            }
            Dijkstra dijkstra = new Dijkstra(graph, 0, H*W-1);
            dijkstra.execute();
            out.println(dijkstra.getRouteCount() % 1000000007);


        }
    }

    public static class Dijkstra {
        private int startPoint;
        private int goalPoint;
        private List<Map<Integer, Integer>> routeMap;
        private int[] routeCount;
        private int[] prev;


        Dijkstra(List<Map<Integer, Integer>> routeMap, int startPoint) {
            this.startPoint = startPoint;
            this.routeMap = routeMap;
            this.goalPoint = -1;

        }

        Dijkstra(List<Map<Integer, Integer>> routeMap, int startPoint, int goalPoint) {
            this.startPoint = startPoint;
            this.routeMap = routeMap;
            this.goalPoint = goalPoint;

        }

        private int getRouteCount() {
            return this.routeCount[this.goalPoint];
        }

        public List<Integer> getPath() {
            List<Integer> path = new ArrayList<>();
            int dest = this.goalPoint;
            path.add(this.goalPoint);
            while (this.prev[dest] != Integer.MAX_VALUE) {
                path.add(prev[dest]);
                dest = prev[dest];
            }
            Collections.reverse(path);
            return path;
        }

        public int[] execute() {
            int numberOfCity = this.routeMap.size();
            int[] dist = new int[numberOfCity];
            this.prev = new int[numberOfCity];
            this.routeCount = new int[numberOfCity];
            for (int i = 0; i < numberOfCity; i++) {
                dist[i] = Integer.MAX_VALUE;
                this.prev[i] = Integer.MAX_VALUE;
                this.routeCount[i] = 0;
            }
            dist[this.startPoint] = 0;
            this.routeCount[this.startPoint] = 1;
            PriorityQueue<Node> pQueue = new PriorityQueue<>();
            pQueue.offer(new Node(this.startPoint, 0));
            while (!pQueue.isEmpty()) {
                Node node = pQueue.poll();
                int prev_cost = node.getCost();
                int src = node.getNode();
                if (dist[src] < prev_cost) {
                    continue;
                }
                for (Map.Entry<Integer, Integer> e : this.routeMap.get(src).entrySet()) {
                    int dest = e.getKey();
                    int cost = e.getValue();

                    if (cost != Integer.MAX_VALUE && dist[dest] > dist[src] + cost) {
                        dist[dest] = dist[src] + cost;
                        this.prev[dest] = src;
                        pQueue.offer(new Node(dest, dist[dest]));
                    }

                    if (dist[dest] == dist[src] + cost) {
                        this.routeCount[dest] += this.routeCount[src] % 1000000007;
                    }

                }
            }

            return dist;

        }

        class Node implements Comparable<Node> {
            private int node;
            private int cost;

            public Node(int node, int cost) {
                this.node = node;
                this.cost = cost;
            }

            @Override
            public int compareTo(Node node2) {
                return Integer.compare(this.cost, node2.cost);
            }

            public int getNode() {
                return this.node;
            }

            public int getCost() {
                return this.cost;
            }
        }

    }


    static int nint(Scanner sc) {


        return Integer.parseInt(sc.next());
    }

    static long nlong(Scanner sc) {
        return Long.parseLong(sc.next());
    }

    static double ndouble(Scanner sc) {
        return Double.parseDouble(sc.next());
    }

    static float nfloat(Scanner sc) {
        return Float.parseFloat(sc.next());
    }

    static String nstr(Scanner sc) {
        return sc.next();
    }

    static long[] longLine(Scanner sc, int size) {
        long[] lLine = new long[size];
        for (int i = 0; i < size; i++) {
            lLine[i] = nlong(sc);
        }
        return lLine;
    }

    static int[] intLine(Scanner sc, int size) {
        int[] iLine = new int[size];
        for (int i = 0; i < size; i++) {
            iLine[i] = nint(sc);
        }
        return iLine;
    }

    static String[] strLine(Scanner sc, int size) {
        String[] strLine = new String[size];
        for (int i = 0; i < size; i++) {
            strLine[i] = nstr(sc);
        }
        return strLine;
    }

    static long maxFromList(List<Long> longList) {
        return longList.stream().max(Comparator.naturalOrder()).get();
    }

    static long minFromList(List<Long> longList) {
        return longList.stream().min(Comparator.naturalOrder()).get();
    }

    public static int sumDigits(int n) {
        int sum = 0;
        while (n != 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    public static long sumDigits(long n) {
        long sum = 0;
        while (n != 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    static List<Integer> getIntegerList(Scanner sc, int size) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            list.add(nint(sc));
        }
        return list;
    }

    static List<Long> getLongList(Scanner sc, int size) {
        List<Long> list = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            list.add(nlong(sc));
        }
        return list;
    }

    static List<String> getStringList(Scanner sc, int size) {
        List<String> stringList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            stringList.add(nstr(sc));
        }
        return stringList;
    }

    private static long lcm(long a, long b) {
        return a * b / gcd(b, a % b);
    }

    private static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private static Map<Integer, Integer> primeFactorize(long num) {
        Map<Integer, Integer> map = new HashMap<>();
        int i = 2;
        while (i * i <= num) {
            while (num % i == 0) {
                num /= i;
                if (map.containsKey(i)) {
                    int tmp = map.get(i);
                    tmp++;
                    map.put(i, tmp);
                } else {
                    map.put(i, 1);
                }
            }
            i++;
        }
        if (num > 1)
            map.put((int) num, 1);
        return map;
    }

    /**
     * Returns the most frequent value in the list. リスト内で最頻出数値を返します。
     *
     * @param list List
     * @return most frequent value
     */
    private static Integer getMode(List<Integer> list) {
        if (list.size() <= 0) {
            throw new IllegalArgumentException();
        }

        Map<Integer, Integer> modeMap = new HashMap<>();

        for (Integer x : list) {
            if (modeMap.containsKey(x)) {
                modeMap.put(x, modeMap.get(x) + 1);
            } else {
                modeMap.put(x, 1);
            }
        }
        return modeMap.entrySet().stream()
                .max(Map.Entry.comparingByValue())
                .get()
                .getKey();

    }
}

Submission status: Runtime Error

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