[AtCoder] H - Grid 1

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : H - Grid 1
Source            : AtCoder Educational DP Contest
Category          : Dynamic Programing
Algorithm         : Dynamic Programing 
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll           long long
 
static const int maxn = 1000 + 5;
static const ll mod = 1e9 + 7;
 
int dr[] = {+0, -1, +0, +1};
int dc[] = {-1, +0, +1, +0};
 
char grid[maxn][maxn];
ll dp[maxn][maxn];
bool memoize[maxn][maxn];
 
int row, column;
 
inline bool inside(int r, int c)
{
      return (r >= 1 && r <= row && c >= 1 && c <= column);
}
 
inline ll solve(int r, int c)
{
      if (r == row && c == column) return 1;
      ll &ret = dp[r][c];
      bool &mem = memoize[r][c];
      if (mem) return ret;
      mem = 1;
      ret = 0;
      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 + solve(rr, cc)) % mod;
      }
      return ret;
}
 
int main()
{
      cin >> row >> column;
      for (int i = 1; i <= row; i++) for (int j = 1; j <= column; j++) cin >> grid[i][j];
      cout << solve(1, 1);
}