【アルゴリズム問題】yukicoder no.13 囲みたい! (level ☆☆☆)
閉じる
閉じる

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

×

【アルゴリズム問題】yukicoder no.13 囲みたい! (level ☆☆☆)

2014-08-10 18:22
    kevinはとあるゲームをしている。
    WH個のマスで構成されるフィールドが与えられる。
    最初にあるマスを選択し、上下左右の同じ数字のみ辿れ、任意の場所で離す事ができる。
    この時、同じ数字のみをたどって、囲みができたら高得点になるゲームである。

    囲みとは、辿ったマスの順番に線をつないだ時に、K(>=4)角形ができていることである。

    フィールドが与えられた時に囲みができるかどうか判定してください。
    囲みが出来る場合 possible 出来ない場合は impossible を出力してください。

    入力
    W H
    M11...Mi1.. MW1
    M12...Mi2.. MW2
    ..............
    M1j...Mij.. MWj
    .............
    M1H...MiH.. MWH

    1行目には 横を表すW(1<=W<=100)と縦を表すH (1<=H<=100)数値が半角スペース区切りで与えられる。
    2行目以降には、各行i列目j行目を表す数値Mij(1<=Mij<=1000)が半角スペース区切りで与えられる。

    出力
    possibleまたはimpossibleを出力してください。

    sample1
    3 3
    1 2 3
    1 1 3
    1 1 4

    ans1
    possible

    左下で1をうまくたどると、4角形ができます。


    sample2
    5 4
    1 2 2 2 3
    2 2 4 2 2
    2 1 1 1 2
    2 2 2 2 2

    ans2
    possible

    2で大きな凸の8角形ができる。



    sample3
    5 4
    5 5 5 3 5
    5 3 1 5 1
    5 2 2 5 8
    5 5 5 5 9

    ans3
    impossible

    このフィールドでは囲みが出来ない。


    sample4
    https://gist.githubusercontent.com/yuki2006/c1858a73b0e7a470a2a9/raw/b87c27bcb55e02e7fa9eb53007f884566cae681c/yukicoder12.txt

    ans4
    possible



    sample5
    https://gist.githubusercontent.com/yuki2006/c1858a73b0e7a470a2a9/raw/70511f7e6e8f2f62d0703ce67ea1e6da559a9ad3/sample5

    ans5
    possible

    提供なおさん。

    q
    https://gist.githubusercontent.com/yuki2006/c1858a73b0e7a470a2a9/raw/49cdf878d122cc52951ad5a770641dfdc764fe6e/yukicoder12.txt

    想定解 Java
    http://ideone.com/jMXghF#


    1st. なおさん C++
    http://ideone.com/Svbnly

    2nd . myonさん Haskell
    Data.Graph使ってるが撃墜ケースあり
    http://ideone.com/DV01JB

    自力でゴリゴリやってAC
    http://ideone.com/vtOSpG


    3nd. scacheさん Java
    http://ideone.com/VmBj5A



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