Grid Paths (DP)

Lab C++ Advanced 30 points

Read a grid of . and # (blocked). Count the paths from the top-left to the bottom-right moving only right or down, modulo 1,000,000,007.

Input

r c, then r rows.

Output

One integer.

Example

Input

3 3
...
.#.
...

Output

Sample input available Sample output available

Editor

C++

Hints

ways[i][j] = ways from above + ways from the left.

Solution explanation

Each cell's answer depends only on two neighbours already computed - classic 2D DP.

Show solution

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    const long long MOD = 1000000007;
    int r, c;
    cin >> r >> c;
    vector<string> g(r);
    for (auto &row : g) cin >> row;
    vector<vector<long long>> ways(r, vector<long long>(c, 0));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (g[i][j] == '#') continue;
            if (i == 0 && j == 0) ways[i][j] = 1;
            if (i > 0) ways[i][j] += ways[i - 1][j];
            if (j > 0) ways[i][j] += ways[i][j - 1];
            ways[i][j] %= MOD;
        }
    }
    cout << ways[r - 1][c - 1] << "\n";
    return 0;
}

Output

Answer