【アルゴリズム問題】yukicoder no.20 砂漠のオアシス by なおさん (レベル☆☆)
閉じる
閉じる

新しい記事を投稿しました。シェアして読者に伝えましょう

×

【アルゴリズム問題】yukicoder no.20 砂漠のオアシス by なおさん (レベル☆☆)

2014-09-01 00:22

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

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

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

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

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

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


    【入力】
    N V OX OY
    L_11 L_21 L_31 ... L_N1
    L_12 L_22 L_32 ... L_N2
    ・・・ ...
    L_1N L_2N L_3N ... L_NN

    1行目
    2 <= N <= 500 : 砂漠の広さ
    1 <= V <= 500 : 太郎君の体力値
    0 <= OX,OY <= N : オアシスの位置 (OX = 0, OY = 0 の場合、オアシスは無い)
    が半角スペース区切りで与えられる。

    2行目以降は
    0 <= L_xy <= 9 : (x,y)の場所の砂漠レベル (1 <= x,y <= N)
    が半角スペース区切りで与えられる。

    【出力】
    たどり着けるなら「YES」、たどり着けないなら「NO」 (括弧は含まない)



    【sample1】
    3 3 0 0
    0 1 1
    2 0 1
    1 2 0

    【ans1】
    YES

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



    【sample2】
    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


    【ans2】
    YES

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


    【sample3】
    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

    【ans3】
    NO

    【sample4】

    https://gist.githubusercontent.com/yuki2006/b4cfb89d0c873c50453a/raw/8eb3ee6215f149a21d3e4a448d924000801a4cf3/sample4.txt

    【ans4】
    NO


    【sample5】
    https://gist.githubusercontent.com/yuki2006/b4cfb89d0c873c50453a/raw/d0686eeb2174917822656e721df654016ac3a99e/sample5.txt

    【ans5】
    YES

    【question】

    https://gist.githubusercontent.com/yuki2006/b4cfb89d0c873c50453a/raw/c63cf328b7506b72381337afbcb2fdc9ee8cfdb1/question.txt


    キーワード:ダイクストラ法、SPFA、幅優先探索、DP

    想定解法

    http://ideone.com/OdolI4
    (SP

    なおさん
    http://melpon.org/wandbox/permlink/v8wF91XXBpKcvg0R
    (SPFA)



    1st. chokudaiさん C#
    http://melpon.org/wandbox/permlink/FKUJE4ibjxfaFSxg

    2nd.scacheさん Java
    http://melpon.org/wandbox/permlink/modLuVndCvu4lu4v

    3rd.くろとんさん C++
    http://melpon.org/wandbox/permlink/xKStuJ3pT5EBT9Bx


    広告
    コメントを書く
    コメントをするには、
    ログインして下さい。