グリッド版ダイクストラ問題セットのサムネイル
問題4: 拡張ダイクストラ - コストを0にできるチケット (paizaランク A 相当)

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

問題

Img 04 03 下記の問題をプログラミングしてみよう!

グリッド状の盤面で上下左右の移動を繰り返して、プレイヤーが左上のスタートから右下のゴールまで移動するときに通るマスのコストの合計の最小値を求めてください。
ただし、1つのマスのコストを0にできるチケットをn枚使えます。

※この問題は、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}
n


・1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・続く h 行の各行では i 行目 (0 ≦ i < h) には、盤面が与えられます。
・t_{i,j} は i 行目の j 列目のコストです。
・最後の行ではチケットの枚数 n が与えられます。


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

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

条件

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

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

入力例1

5 12
0 1 1 1 9 9 9 9 1 1 1 1
1 1 1 1 1 9 9 9 1 9 9 1
1 1 1 9 9 9 9 9 1 9 9 1
9 2 9 9 1 1 1 1 1 9 9 1
1 1 1 2 1 9 9 9 9 9 9 1
0

出力例1

25

入力例2

5 12
0 1 1 1 9 9 9 9 1 1 1 1
1 1 1 1 1 9 9 9 1 9 9 1
1 1 1 9 9 9 9 9 1 9 9 1
9 2 9 9 1 1 1 1 1 9 9 1
1 1 1 2 1 9 9 9 9 9 9 1
1

出力例2

20

問題一覧へ戻る

ページの先頭へ戻る