Submission #18423275

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;


typedef long long int ll;

const ll mod = 1000000000 + 7;

int main() {
    ll h,w; cin >> h >> w;
    vector<string> f(h);
    for (int i = 0; i < h; i++) {
        cin >> f[i];
    }

    vector<vector<ll> > sum_u(h, vector<ll>(w, 0));
    vector<vector<ll> > sum_y(h, vector<ll>(w, 0));
    vector<vector<ll> > sum_n(h, vector<ll>(w, 0));
    vector<vector<ll> > memo(h, vector<ll>(w, 0));
    memo[0][0] = 1;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (i == 0 && j == 0) { continue; }
            if (f[i][j] == '#') {
                memo[i][j] = 0;
                continue;
            }
            // ue
            ll ue = 0;
            if (i > 0 && f[i-1][j] != '#') {
                sum_u[i - 1][j] = (i > 1 ? sum_u[i - 2][j] : 0) + memo[i-1][j];
                ue = sum_u[i-1][j];
            }
            // yoko
            ll yoko = 0;
            if (j > 0 && f[i][j-1] != '#') {
                sum_y[i][j - 1] = (j > 1 ? sum_y[i][j - 2] : 0) + memo[i][j - 1];
                yoko = sum_y[i][j-1];
            }
            // naname
            ll naname = 0;
            if (i > 0 && j > 0 && f[i-1][j-1] != '#') {
                sum_n[i - 1][j - 1] = (i > 1 && j > 1 ? sum_n[i - 2][j - 2] : 0) + memo[i - 1][j - 1];
                naname = sum_n[i - 1][j-1];
            }
            memo[i][j] = (ue + yoko + naname) % mod;
        }
    }
    cout << memo[h-1][w-1] << endl;
    return 0;
}

Submission Info

Judge Result