問題3: ダイクストラ法 - 経路復元 (paizaランク A 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

グリッド状の盤面で上下左右の移動を繰り返して、プレイヤーが左上のスタートから右下のゴールまで移動するときに通るマス (スタート、ゴール含む) のコストの合計の最小値を求めてください。
さらに対応する経路をゴールからスタートまでの順序で出力してください。なお、コストが最小になるような経路は 1 つであることが保証されます。

※この問題は、paiza開発日誌で詳しく解説しています

入力される値

h w
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}

・ 1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・続く h 行のうち i 行目には、i 行目のマスのコストを表す整数値のリスト t_i が与えられます。
・ t_{i,j} は i 行目の j 列目のコストです。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力

コストの合計の最小値を 1 行目に出力してください。

続けて、ゴールからスタートまでの経路を以下のように盤面の並びとして出力してください。

--
盤面_1
--
盤面_2
...
--
盤面_n

・ n は最短経路上のマスの数です。
・盤面_k (1 ≦ k ≦ n) はゴールからいくつ前のマスにプレイヤーがいるかを表しています。
・盤面_1 はゴールのマスにプレイヤーがいることを表す盤面です。

盤面_k (1 ≦ k ≦ n) は次の形式で出力してください。

 t_{0,0} t_{0,1} ... t_{0,w-1}
 t_{1,0} t_{1,1} ... t_{1,w-1}
 ...
 t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}

・ t_{i,j}の左には半角スペースを出力してください。
・ただし、通るマスにプレイヤーがいるマスの左には、半角スペースの代わりに*を出力してください。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ h , w ≦ 20
・ 0 ≦ t_{i,j} ≦ 100 (0 ≦ i < h, 0 ≦ j < w)

入力例1: 3 6
0 3 1 4 1 5
9 2 6 5 3 5
3 9 7 9 3 2

出力例1: 17
--
0 3 1 4 1 5
9 2 6 5 3 5
3 9 7 9 3*2
--
0 3 1 4 1 5
9 2 6 5 3 5
3 9 7 9*3 2
--
0 3 1 4 1 5
9 2 6 5*3 5
3 9 7 9 3 2
--
0 3 1 4*1 5
9 2 6 5 3 5
3 9 7 9 3 2
--
0 3 1*4 1 5
9 2 6 5 3 5
3 9 7 9 3 2
--
0 3*1 4 1 5
9 2 6 5 3 5
3 9 7 9 3 2
--
0*3 1 4 1 5
9 2 6 5 3 5
3 9 7 9 3 2
--
*0 3 1 4 1 5
9 2 6 5 3 5
3 9 7 9 3 2

問題一覧へ戻る