Count the number of shortest path

Given a grid and two nodes (say A & B) on the grid which is h units apart horizontally and v units apart vertically, give the count of number of shortest path along the grid lines between A & B.

For example, take the case below where A & B are 1 unit apart horizontally and 1 unit apart vertically i.e. h = 1 and v = 1.

In this case, the answer is 2 as shown below:

Give your answer in terms of h and v for the generic case.

 

using System;

using System.Collections.Generic;

using System.Text;

using System.IO;

using System.Collections;

 

namespace ConsoleApplication1

{

    class Coordinate

    {

        public int x;

        public int y;

        public Coordinate(int x, int y)

        {

            this.x = x;

            this.y = y;

        }

    }

    class Program

    {

        static void Main(string[] args)

        {

            //Enter horizontal distance

            Console.Write("Enter Horizontal Distance: ");

            string hdStr = Console.ReadLine();

            int hd = int.Parse(hdStr);

            //Enter vertical distance

            Console.Write("Enter Vertical Distance: ");

            string vdStr = Console.ReadLine();

            int vd = int.Parse(vdStr);

            //Initializing starting node

            Coordinate start = new Coordinate(0, 0);

            //Initializing ending node

            Coordinate end = new Coordinate(hd, vd);

            int numberOfShortestPath = 0;

            //Calculating number of nodes in shortest path

            int numNodes = hd + vd – 1;

            //Calculating number of intermediate coordinates in the grid

            int pointCount = (hd + 1) * (vd + 1) – 2;

            Coordinate[] gridPoint = new Coordinate[pointCount];

            pointCount = 0;

            //Initializing grid points

            for (int i = 0; i <= hd; i++)

            {

                for (int j = 0; j <= vd; j++)

                {

                    if (!((i == 0 && j == 0) || (i == hd && j == vd)))

                    {

                        gridPoint[pointCount] = new Coordinate(i, j);

                        pointCount++;

                    }

                }

            }

            //Create numNodes combinations out of gridPoint.Count and validate

            int[] pointer = new int[numNodes];

            //Initializing the pointer array

            for (int i = 0; i < numNodes; i++)

            {

                pointer[i] = i;

            }

            pointer[numNodes – 1]–;

            //Permutation loop

            do

            {

                int i = numNodes – 1;

            label1:

                pointer[i]++;

                if (pointer[i] == gridPoint.Length && i != 0)

                {

                    pointer[i] = 0;

                    i–;

                    goto label1;

                }

                else if (pointer[i] == gridPoint.Length && i == 0)

                {

                    break;

                }

                else

                {

                    //Check pointer validity

                    int[] counter = new int[gridPoint.Length];

                    int flag = 0;

                    for (i = 0; i < numNodes; i++)

                    {

                        counter[pointer[i]]++;

                        if (counter[pointer[i]] > 1)

                        {

                            flag = 1;

                            break;

                        }

                    }

                    if (flag == 0)

                    {

                        if (Check(start, gridPoint[pointer[0]]) && Check(end, gridPoint[pointer[numNodes – 1]]))

                        {

                            bool correct = true;

                            for (i = 0; i < numNodes – 1; i++)

                            {

                                if (!Check(gridPoint[pointer[i]], gridPoint[pointer[i + 1]]))

                                {

                                    correct = false;

                                }

                            }

                            if (correct)

                            {

                                numberOfShortestPath++;

                            }

                        }

                    }

                }

            } while (pointer[0] != gridPoint.Length);

            Console.WriteLine("Number of Shortest Path = " + numberOfShortestPath);

        }

        public static bool Check(Coordinate point1, Coordinate point2)

        {

            //Horizontal Check

            if ((Math.Abs(point1.x – point2.x) == 1) && point1.y == point2.y)

            {

                return true;

            }

            //Vertical Check

            else if ((Math.Abs(point1.y – point2.y) == 1) && point1.x == point2.x)

            {

                return true;

            }

            else

            {

                return false;

            }

        }

    }

}

 

Enter Horizontal Distance: 3
Enter Vertical Distance: 3
Number of Shortest Path = 20
Press any key to continue . . .

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s