CODEWITHSUNDEEP
pathshortest
687gaint
687gaint

Reputation: 51

Kth shortest path in a given MAZE c++

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 after sorting the vector printed the Kth value in vector...But i need more efficient way to solve the problem ..can dynamic programming be used here..???

Upvotes: 0

Views: 1018

Answers (1)

Ranald Lam
Ranald Lam

Reputation: 496

I have a dynamic programming solution for this.

Use a 3D matrix cost[M][N][K] where cost[x][y][i] will represent the ith shortest path to reach cell (x, y) from the top right hand corner.

Notice that each cell (x, y) can only be reached from cell (x-1, y) and (x, y-1). Therefore, we can process the cells in sequential order using for loops. This will ensure cell (x-1, y) and (x, y-1) will be processed before cell (x, y) for any cell (x, y).

for (int x = 0; x < m; x++) {
    for (int y = 0; y < n; y++) {
       //Process
    }
}

Assuming we have already computed all the k shortest path for cell (x-1, y) and (x, y-1), you can compute the k shortest path for cell (x, y) by sorting the 2*k shortest paths leading to cell (x-1, y) and (x, y-1) by picking the smallest cost ones and adding the cost of reaching cell (x, y) to the picked paths. This can be done using a conventional sorting algorithm yielding O(k log k) time per cell. However, since the k shortest paths for cell (x-1, y) and (x, y-1) are already sorted, one can actually sort them in O(k) running time by using a technique similar to mergesort if the time limit is really tight. This yields a best possible run time of O(nmk) and memory O(nmk).

Memory can be reduced by only saving the last row since only the x-1 row is required when computing the xth row, hence we can discard all the rows before the x-1 row.

Upvotes: 1

Related Questions