問題一覧 > 通常問題

No.20 砂漠のオアシス

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 242
作問者 : なおなお
10 ProblemId : 64 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-06-23 14:35:10

問題文

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

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

砂漠は際限なく続いていますが、太郎君が知っているのは \(N \times N\) マスの範囲だけで、
その外側に行くと命の危険があるため絶対に行きません。
砂漠の中には、\((O_x,O_y)\)の場所にオアシスがありこの場所へ行くと、
「1度だけ」体力を現在の値の「\(2\)倍」にすることができます。初期の体力を超えても良い。
(オアシスが無い場合もあります)

いま太郎君は \((1,1)\) の場所に立っており、次の街は \((N,N)\) の場所にあります。
太郎君は、辺を共有する前後左右の隣接マスへのみ移動することができ、
次のマスへ移動すると、移動した先の砂漠レベル\((L_{xy})\)分の体力が減ります。
移動先の砂漠レベルが\(0\)の場合、体力値は減りませんが、
太郎君の体力が\(0\)以下になった時点で太郎君が死んでしまいます。

オアシスがある場所にも砂漠レベルが\(1\)以上ある場合もあり、
その場合は砂漠レベル分の体力が減った後に、オアシスの効果が適用されます。

太郎君が次の街へ無事たどり着けるか教えてあげてください。

オアシスが$(1,1)$にあることはない。

入力

\(N\ V\ O_x\ O_y\)
\(L_{11}\ L_{21}\ L_{31}\ \dots\ L_{N1}\)
\(L_{12}\ L_{22}\ L_{32}\ \dots\ L_{N2}\)
\(\dots\)
\(L_{1N}\ L_{2N}\ L_{3N}\ \dots\ L_{NN}\)

\(1\)行目に、
砂漠の1辺の長さを表す整数$N$ \((2 \leq N \leq 200)\)、
太郎君の体力値を表す整数$V$ \((1 \leq V \leq 500)\)、
オアシスの位置を表す整数の組$N$ \((1 \leq O_x,O_y \leq N)\), $(O_x,O_y)$ は $(1,1)$が与えられることはなく、$(O_x,O_y) = (0,0)$の場合はオアシス無しである。
がスペース区切りで与えられる。
\(2\)行目以降は
\(0 \leq L_{xy} \leq 9 : (x,y)\)の場所の砂漠レベル\((1 \leq x,y \leq N)\)
が半角スペース区切りで与えられる。

出力

たどり着けるなら「YES」、たどり着けないなら「NO」を出力してください。 (括弧は含まない)
最後に改行してください。

サンプル

サンプル1
入力
3 3 0 0
0 1 1
2 0 1
1 2 0
出力
YES

\(O_x = 0\) かつ \(O_y = 0\) なので、この場合オアシスはありません。
\((1,1)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(3,2)\rightarrow(3,3)\) の順に歩くのが最も体力を減らさずに行けます。
必要となる体力は \(2\) なので、目的地にたどり着くことができます。

サンプル2
入力
10 3 8 6
0 9 0 0 0 9 0 0 0 9
0 9 0 9 0 0 0 9 0 0
0 9 0 9 9 9 9 9 9 0
0 9 0 9 0 0 0 9 0 0
0 9 0 9 0 9 0 0 9 0
0 9 0 0 0 0 9 1 9 0
0 9 9 0 9 9 9 9 0 0
0 9 0 0 0 0 0 0 9 0
0 9 9 9 9 9 9 0 9 1
0 0 0 0 0 0 0 0 9 2
出力
YES

途中までは砂漠レベルが\(0\)のマスを通って行けるので、まったく減らさずに行けますが、
目的地直前で体力が合計 \(3\) 減るため、途中でオアシスによって行かなければなりません。
オアシスに寄ると、体力が\(3\)から\(1\)減りさらにオアシス効果により\(2\)倍となるため、
体力が\(4\)になります。そのため、目的地にたどり着くことができます。

サンプル3
入力
10 30 8 8
0 1 1 9 7 6 1 1 1 1
1 5 1 4 6 7 1 1 3 1
1 1 5 6 6 6 1 1 0 1
0 1 5 6 7 1 0 7 9 1
2 1 5 6 7 1 9 8 1 1
1 1 5 5 5 0 9 9 1 5
1 1 4 5 4 1 9 9 2 1
1 2 3 4 1 0 9 9 4 6
5 1 2 1 1 1 9 8 1 2
1 1 1 1 1 1 9 3 9 1
出力
NO

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