No.34 砂漠の行商人

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.34 砂漠の行商人

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 168
作問者 :

なお

6 ProblemId : 15 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2015-11-14 17:46:54

問題文

太郎君は砂漠を歩く行商人です。
太郎君はこれから次の街へ行こうとしています。

砂漠には移動しやすい場所とそうでない場所があり、
太郎君は長年の経験から、
その場所に行くとどれくらいの体力を消耗するかを知っています。

砂漠は際限なく続いていますが、太郎君が知っているのは $N \times N$ マスの範囲だけで、
その外側に行くと命の危険があるため絶対に行きません。

いま太郎君は体力 $V$ で $(S_{X}, S_{Y})$ の場所に立っており、次の街は $(G_{X}, G_{Y})$ の場所にあります。
太郎君は、辺を共有する前後左右の隣接マスへのみ移動することができ、
今居るマスから隣のマスへ移動するときに $1$ 回の移動とみなし、
さらに、移動した先の砂漠レベル $(L_{X Y})$ 分の体力が減ります。
移動先の砂漠レベルが $0$ の場合、体力値は減りませんが、
太郎君の体力が $0$ 以下になった時点で太郎君が死んでしまいます。
街に着いた瞬間に死んでしまってもいけません。

太郎君は、商品をできるだけ早く捌きたいので、
「太郎君が死なずに」「最も早く次の街へ着く」には、
どれくらい時間がかかるか計算してください。

入力

 $N V S_{X} S_{Y} G_{X} G_{Y}$ 
 $L_{11} L_{21} L_{31} \dots L_{N 1}$ 
 $L_{12} L_{22} L_{32} \dots L_{N 2}$ 
 $\dots$ 
 $L_{1 N} L_{2 N} L_{3 N} \dots L_{N N}$

$1$ 行目に、砂漠の1辺の長さを表す整数 $N (3 \leq N \leq 100)$ 、
太郎君の体力値を表す整数 $V (1 \leq V \leq 10000)$ 、
太郎君の初期位置を表す整数の組 $(S_{X}, S_{Y}) (1 \leq S_{X}, S_{Y} \leq N)$ 、
次の街の位置を表す整数の組 $(G_{X}, G_{Y}) (1 \leq G_{X}, G_{Y} \leq N)$ 、
がスペース区切りで与えられます。
続く $N$ 行に、それぞれの場所の砂漠レベル $L_{X Y} (0 \leq L_{X Y} \leq 9)$ が空白区切りで与えられます。

初期位置 $(S_{X}, S_{Y})$ と次の街の位置 $(G_{X}, G_{Y})$ は、同じ座標になることはありません。

出力

太郎君が死なずに、最も早く次の街へ着く最小の移動回数。
どうやっても生きてたどり着けない場合は $- 1$ を出力すること。
最後に改行すること。

サンプル

サンプル1

入力

3 2 1 1 3 1
0 2 0
0 1 0
0 0 0

出力

遠回りすれば体力を減らさずに着くことができますが、移動回数 $6$ が必要です。
(1,1)→(2,1)→(3,1) の順に歩くと移動回数 $2$ ですが、途中で死んでしまうためダメです。
(1,1)→(1,2)→(2,2)→(3,2)→(3,1) の順に歩くのが、死なない範囲で最も早く着くことができます。

サンプル2

入力

4 25 1 1 4 4
0 1 3 3
1 4 1 5
2 2 7 8
6 7 4 9

出力

-1

どのような経路でも途中で死んでしまうため、次の街へ着くことができません。

サンプル3

入力

21 40 15 1 18 21
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 4 3 9 0 4 4 3 0 8 7 0 2 2 2 3 8 1 2 1 2
2 5 6 3 4 9 1 2 2 6 6 8 0 1 1 0 9 8 4 6 3
6 5 0 7 9 9 7 2 9 4 3 0 9 7 5 9 0 4 1 9 5
3 9 2 1 8 4 7 9 8 0 3 9 5 1 2 1 2 5 9 8 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 1 7 9 5 2 3 0 4 0 8 4 4 8 5 4 2 8 3 8 6
3 9 6 7 3 0 4 1 9 5 1 2 2 3 0 8 0 6 6 4 4
3 6 6 6 7 4 5 3 0 6 7 3 5 1 9 3 0 5 9 9 9
8 1 1 4 2 5 9 3 2 4 1 8 4 6 3 5 5 3 3 6 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 5 7 7 9 2 8 4 5 6 4 6 8 2 7 3 5 8 5 2 4
9 0 7 7 0 4 1 6 1 9 1 5 0 1 6 5 2 6 6 6 5
3 9 7 7 2 6 3 7 1 5 3 8 9 5 6 3 4 8 7 3 4
8 9 1 0 3 9 4 3 9 1 4 8 1 0 5 9 4 3 6 1 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 5 0 0 4 9 3 9 6 5 4 2 1 5 9 8 7 8 8 6 3
7 2 3 9 9 9 7 7 0 5 8 0 6 3 6 1 2 3 1 0 5
7 8 1 1 8 5 4 3 5 0 2 5 8 5 3 5 3 4 1 0 7
7 1 8 1 2 0 5 8 1 3 9 6 1 3 8 3 9 4 8 6 8
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

出力

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder

No.34 砂漠の行商人

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力