[toph.co] Easy Path

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Easy Path
Source            : toph.co
Category          : Dynamic Programing, Combinatorics
Algorithm         : nCr
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
#define MOD              1000000007
 
static const int MAXN = 1e6 + 6;
 
typedef long long ll;
 
vector <char> grid[MAXN];
vector <ll> upor[MAXN], nich[MAXN];
vector <bool> visupor[MAXN], visnich[MAXN];
int N, M;
 
int dr[] = {+0, +1, +0, -1};
int dc[] = {+1, +0, -1, +0};
 
bool inside(int r, int c)
{
    return r >= 1 && r <= N && c >= 1 && c <= M;
}
 
ll UP(int r = 1, int c = 1)
{
    //if (!inside(r, c) || grid[r][c] == '.')
    //    return 0;
 
    if (r == N && c == M)
    {
        upor[r][c] = 1;
        return 1;
    }
    ll &ret = upor[r][c];
    if (visupor[r][c]) return ret;
    visupor[r][c] = 1;
    for (int i = 0; i < 2; i++)
    {
        int rr = r + dr[i];
        int cc = c + dc[i];
        if (inside(rr, cc) && grid[rr][cc] == '#')
            ret = (ret + UP(rr, cc)) % MOD;
    }
    return ret % MOD;
}
 
ll DOWN(int r = N, int c = M)
{
    //if (!inside(r, c) || grid[r][c] == '.')
    //    return 0;
 
    if (r == 1 && c == 1)
    {
        nich[r][c] = 1;
        return 1;
    }
    ll &ret = nich[r][c];
    if (visnich[r][c]) return ret;
    visnich[r][c] = 1;
    for (int i = 2; i < 4; i++)
    {
        int rr = r + dr[i];
        int cc = c + dc[i];
        if (inside(rr, cc) && grid[rr][cc] == '#')
            ret = (ret + DOWN(rr, cc)) %MOD;
    }
    return ret %MOD;
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        grid[i].resize(M+1);
        for (int j = 1; j <= M; j++)
        {
            cin >> grid[i][j];
        }
    }
    for (int i = 0; i <= N; i++)
    {
        upor[i].resize(M+1, 0);
        nich[i].resize(M+1, 0);
        visupor[i].resize(M+1, 0);
        visnich[i].resize(M+1, 0);
    }
    int  Q;
    cin >> Q;
    UP();
    DOWN();
    while (Q--)
    {
        int L;
        cin >> L;
        ll ans = 0;
        for (int i = 0; i < L; i++)
        {
            int x, y;
            cin >> x >> y;
            ll res = (upor[x][y] * nich[x][y]) %MOD;
            ans += res;
            ans %= MOD;
        }
        cout << ans << "\n";
    }
}