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 . . .