Kth shortest path in a given MAZE c++

Vote count:

0

You are given a cost matrix of dimensions m X n.The problem is to find the minimal path from top-left corner to some cell in the matrix.The total cost of a path is sum total of cost of all cells visited in the path.Only 2 moves are allowed: either to go down by a row, or move right by a column. You cannot leave the matrix at any time Also, some of the cells are marked as obstacles and cannot be stepped upon. Several queries of the form: tx ty k are to be answered. The output for this query should be kth minimum cost of a path from top-left corner to cell indexed at ty column in tx row CONSTRAINTS:

1<= m,n <= 100 0 <= tx < m 0 <= ty <n 1 <= k <= 101 
The obstacles in matrix are marked by "##" (quotes only for clarity) 
The values in every cell that is not an obstacle, varies from -9 to 99 only. 
tx and ty are both 0-indexed. 
If k exceeds the total paths to cell (tx, ty) output "Not so many paths" 
If (tx, ty) is an obstacle, output "Obstacle". 
There will never be an obstacle on the top-left corner or bottom-right corner.


Input: 
 The first line contains the number of test cases T, 
 The first line of each test case contains two space-separated integers m and n. 
 The next m lines each contain n integers, denoting the matrix. 
 The next line contains an integer q, denoting the number of queries to come. 
 The next q lines each contain 3 space separated integers, tx ty and k 
Output: 
 For each query output the kth shortest path 

What i tried is backtracking which resulted in TLE.(time limit was given 1 sec).Whenever i reach the destination cell i stored that path cost in vector..and in the end printed the Kth value in vector...But i need more efficient way to solve the problem ..can dynamic programming be used here..???

asked 53 secs ago

unknown__

3

Kth shortest path in a given MAZE c++