0

给定一个维度为 m X n 的成本矩阵。问题是找到从左上角到矩阵中某个单元格的最小路径。路径的总成本是路径中访问的所有单元格的成本总和. 只允许 2 次移动：要么向下移动一行，要么向右移动一列。任何时候你都不能离开矩阵此外，一些细胞被标记为障碍物，不能被踩到。需要回答以下形式的几个查询： tx ty k。此查询的输出应该是从左上角到在 tx 行约束中的 ty 列索引的单元格的路径的第 k 个最小成本：

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

我尝试的是导致 TLE 的回溯。（时间限制为 1 秒）。每当我到达目标单元格时，我将路径成本存储在向量中。最后在对向量进行排序后打印向量中的第 K 个值。 .但我需要更有效的方法来解决问题..可以在这里使用动态编程..???

4

1 回答 1

1

我有一个动态编程解决方案。

使用 3D 矩阵cost[M][N][K]，其中cost[x][y][i]将表示从右上角到达单元格 (x, y) 的第 i 个最短路径。

请注意，每个单元格 (x, y) 只能从单元格 (x-1, y) 和 (x, y-1) 到达。因此，我们可以使用 for 循环按顺序处理单元格。这将确保单元格 (x-1, y) 和 (x, y-1) 将在任何单元格 (x, y) 的单元格 (x, y) 之前处理。

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

假设我们已经计算了单元格 (x-1, y) 和 (x, y-1) 的所有 k 条最短路径，您可以通过对 2*k 条最短路径进行排序来计算单元格 (x, y) 的 k 条最短路径通过选择最小的成本并将到达单元格 (x, y) 的成本添加到选择的路径中，导致单元格 (x-1, y) 和 (x, y-1)。这可以使用传统的排序算法来完成，每个单元格产生 O(k log k) 时间。但是，由于单元格 (x-1, y) 和 (x, y-1) 的 k 条最短路径已经排序，实际上可以通过使用类似于合并排序的技术在 O(k) 运行时间内对它们进行排序，如果时间限制真的很紧。这产生了 O(nmk) 和内存 O(nmk) 的最佳运行时间。

只保存最后一行可以减少内存，因为在计算第 x 行时只需要 x-1 行，因此我们可以丢弃 x-1 行之前的所有行。

于 2014-09-01T17:26:01.920 回答