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

これには動的プログラミングソリューションがあります。

右上隅からセル (x, y) に到達するための i 番目の最短経路を表す3D マトリックスを使用しcost[M][N][K]ます。cost[x][y][i]

各セル (x, y) は、セル (x-1, y) および (x, y-1) からのみ到達できることに注意してください。したがって、for ループを使用してセルを順番に処理できます。これにより、セル (x, y) のセル (x, y) の前に、セル (x-1, y) と (x, y-1) が処理されることが保証されます。

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-1, y) および (x, y-1) に至るには、コストが最も小さいものを選択し、選択したパスにセル (x, y) に到達するコストを追加します。これは、セルあたり 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 に答える