Educational DP Contest H - Grid 1

 Educational DP Contest  H - Grid 1

Proble Lnk :https://atcoder.jp/contests/dp/tasks/dp_h

Procedure:
We have to find the number of Taro's paths from Square 
(1,1) to
(H,W), modulo 109+7.  We can find it simply by using DP.  
If we go for(i,j) then we know (i,j) can be reached only from 
(i-1,j) or(i,j-1) unless these two paths contains '#'.  
After completing every step we will find the number of paths.

Solution

#include<bits/stdc++.h>
using namespace  std ;
typedef long long  ll;
typedef pair<ll, ll> Pll;
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define rad(X) cout << (X) << endl
#define ASH(X) cout << (X) << " "
#define debug(x) cout << #x << " " << x << endl;
#define debug2(x,y) cout << #x << " " << x << " " << #y << " " << y << endl;
#define FOR(I,A,B) for(ll I = (A); I <= (B); I++)
#define cir(I,B,A) for(ll I = (A); I >=(B); I--)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define SORT(c) (sort(c.begin(),c.end()))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASES int ___T; cin >> ___T; for(int cs=1;cs<=___T;cs++)
#define FAST()  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
template<typename T>T gcd(T x, T y){if(y==0)return x;else return gcd(y,x%y);}
ll fx[] = {1, 1, 0, -1, -1, -1, 0, 1};
ll fy[] = {0, 1, 1, 1, 0, -1, -1, -1};
vector<ll>a,b,c;
map<ll,ll>m1,m2,m3;
ll mod =    1e9 + 7;
char  s[1001][1001];
ll   dp[1001][1001];

/************************************************/

void Execute()
{
    ll n, nb, k, q, a, b, c, l, r, d, x, y, p, m,i,j;

      cin >> r >> c;

      FOR(i,0,r-1)FOR(j,0,c-1){
        cin >> s[i][j];
      }


            dp[0][0] = 1;

            FOR(i,0,r-1) FOR(j,0,c-1){
              if(s[i][j]=='#') continue;
              if(i-1>=0) dp[i][j] = (dp[i][j]+dp[i-1][j])%mod;
              if(j-1>=0) dp[i][j] = (dp[i][j]+dp[i][j-1])%mod;
            }

            std::cout << dp[r-1][c-1] << '\n';

}

int32_t main()
{
    //#ifndef ONLINE_JUDGE
    //freopen("atomm.txt", "r", stdin);
    //#endif

    FAST();
  //  CASES
    //{
        Execute();
    //}
}