Longest Possible Route: TCS CodeVita 2016 Question

Problem : Longest Possible Route

Given an MxN matrix, with a few hurdles arbitrarily placed, calculate the cost of longest possible route from point A to point B within the matrix.

Input Format:

1. First line contains 2 numbers delimited by whitespace where, first number M is number of rows and second number N is number of columns
2. Second line contains number of hurdles H followed by H lines, each line will contain one hurdle point in the matrix.
3. Next line will contain point A, starting point in the matrix.
4. Next line will contain point B, stop point in the matrix.

Output Format:

Output should display the length of the longest route from point A to point B in the matrix.

Constraints:

1. The cost from one position to another will be 1 unit.
2. A location once visited in a particular path cannot be visited again.
3. A route will only consider adjacent hops. The route cannot consist of diagonal hops.
4. The position with a hurdle cannot be visited.
5. The values MxN signifies that the matrix consists of rows ranging from 0 to M-1 and columns ranging from 0 to N-1.
6. If the destination is not reachable or source/ destination overlap with hurdles, print cost as -1.

Sample Input and Output

SNo.	Input	Output	Explaination
1	3 10 3 1 2 1 5 1 8 0 0 1 7	24	Here matrix will be of size 3x10 matrix with a hurdle at (1,2),(1,5 ) and (1,8) with starting point A(0,0) and stop point B(1,7) 3 10 3 -- (no. of hurdles ) 1 2 1 5 1 8 0 0 -- (position of A) 1 7 -- (position of B) So if you examine matrix below shown in Fig 1, total hops ( ->) count is 24. So final answer will be 24. No other route longer than this one is possible in this matrix.
2	2 2 1 0 0 1 1 0 0	-1	No path is possible in this 2*2 matrix so answer is -1