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:
- First line contains 2 numbers delimited by whitespace where, first number M is number of rows and second number N is number of columns
- Second line contains number of hurdles H followed by H lines, each line will contain one hurdle point in the matrix.
- Next line will contain point A, starting point in the matrix.
- 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.
Output should display the length of the longest route from point A to point B in the matrix.
Constraints:
- The cost from one position to another will be 1 unit.
- A location once visited in a particular path cannot be visited again.
- A route will only consider adjacent hops. The route cannot consist of diagonal hops.
- The position with a hurdle cannot be visited.
- The values MxN signifies that the matrix consists of rows ranging from 0 to M-1 and columns ranging from 0 to N-1.
- If the destination is not reachable or source/ destination overlap with hurdles, print cost as -1.
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 |

No comments :
Post a Comment