Grid Paths

Consider an n×n grid whose squares may have traps. It is not allowed to move to a square with a trap.

Your task is to calculate the number of paths from the upper-left square to the lower-right square where you only can move right or down.

Example:

Input:  n = 4, arr = {"....", ".*..", "...*", "*..."}
Output: 3

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int gridPaths(int n, vector<string> &arr)
{

    int dp[n + 1][n + 1];
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            char c = arr[i - 1][j - 1];

            if (c == '*')
                continue;
            dp[i][j] = (i == 1 && j == 1) ? 1 : (dp[i - 1][j] + dp[i][j - 1]) % MOD;
        }
    }
    return dp[n][n];
}

int main()
{
    int n = 4;

    vector<string> arr = {"....",
                          ".*..",
                          "...*",
                          "*..."};

    cout << gridPaths(n, arr) << "\n";

    return 0;
}