/ Coding

When Top Left to Bottom Rights Send You Running for Cover

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));
            Console.ReadLine();
        }

        /// <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];
        }
    }
}
When Top Left to Bottom Rights Send You Running for Cover
Share this

Subscribe to Coding Today

Popular queries