## Problem Statement

Given an [n x m] grid consisting of values 0 and 1.
A value of 1 means that you can enter that cell and 0 implies that entry to that cell is not allowed.
You start at the upper-left corner of the grid (1, 1) and you have to reach the bottom-right corner (n, m) such that you can only move in the right or down direction from every cell.
Your task is to calculate the total number of ways of reaching the target.

Constraints :-
1<=n, m<=10, 000

## Solution Approach

We are using a simple approach where we use a 2-D array for storing the number paths for each element by considering the source as only two directions from left or top (given that we are allowed to travel only right or bottom). In the end, we return the bottom right output.

``````using System;

namespace Preparations
{
class Program
{
public static void Main(string[] args)
{
/*
Problem Statement:
Given an [n x  m] grid consisting of values 0 and 1.
A value of 1 means that you can enter that cell and 0 implies that entry to that cell is not allowed.
You start at the upper-left corner of the grid (1, 1) and you have to reach the bottom-right corner (n, m) such that you can only move in the right or down direction from every cell.
Your task is to calculate the total number of ways of reaching the target.

Constraints :-
1<=n, m<=10, 000
*/

var n = 3;
var m = 4;
var grid = new[,] { { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 } };
// Get Total Number of Ways
Console.WriteLine("Total Number Of Ways: " + TotalNumberOfWays(grid, n, m));
}

/// <summary>
/// Calculates Total number of ways by iterating paths in the result grid
/// </summary>
/// <param name="grid">input grid</param>
/// <param name="n">width</param>
/// <param name="m">height</param>
/// <returns>the total number of paths to bottom right block</returns>
private static int TotalNumberOfWays(int[,] grid, int n, int m)
{
// Initialize result Grid to store the ways
var resultGrid = new int[n, m];
resultGrid[0, 0] = grid[0, 0];

// Loop and update the resultGrid based on the directions right and bottom
for (var i = 0; i < n; i++)
{
for (var j = 0; j < m; j++)
{
// allow only if grid element is one
if (grid[i, j] == 0)
{
continue;
}

// covers the case when traveled to the current node from the left direction
if (i - 1 >= 0 && grid[i - 1, j] != 0)
{
resultGrid[i, j] += resultGrid[i - 1, j];
}

// covers the case when traveled to the current node from the top direction
if (j - 1 >= 0 && grid[i, j - 1] != 0)
{
resultGrid[i, j] += resultGrid[i, j - 1];
}
}
}

// return the result grid value in the bottom right
return resultGrid[n - 1, m - 1];
}
}
}
``````