0490 - *さんじげんくうかんのなかにいる*

時間制限 1 秒 / メモリ制限 64 MB / 得点 10 / Writer root / x 20 / 統計 /


TLE
1sec
MLE
64MB
得点
10

爽やかなすとーりー(Tekito)

あなたは○○の城○ピュ○であの海賊のかたがあれなフラッ○ターに乗っています。

( ゜д゜ )彡そう! θを助けに40秒(4秒以外はあいさつ)で支度していざ!!!!!!!!!!

ところがどっこい!!!!!!!!そこには異次元の境界が!!!

どうやら3次元格子の迷路に閉じ込められてしまったよう…どうしたらいいのか…

...何だろう、何かささやいてくるぞ…

(必ず出口はある(あるとはいってない)、同じ境界を探すのだ…そうしなければ間に合わないぞ…)と。

プリッ…なんか取得したぞ?(^p^)う゛あ゛wな゛ん゛ら゛こ゛え゛wwwww地図だ!!わかりずら(ズラ的なノリ)!

こうもしてられないよね、早く出口を探さなきゃっ!

その点フラッ○ターってすげぇよな、どこでも移動可n(ry

問題ですYO!!!

迷路の大きさ h(高さ),d(縦),w(横) が与えられる。
そのあと、地図が与えられるので、始点から終点への最短経路を求めよ!!

あなたは前、後、右、左、上、下の6方向に移動できるとする。

入力

h d w
m0,0,0 m0,0,1 ...... m0,0,w - 1
m0,1,0 m0,1,1 ...... m0,1,w - 1
......
......
m0,d - 1,0 m0,d - 1,1 ...... m0,d - 1,w - 1

m1,0,0 m1,0,1 ...... m1,0,w - 1
m1,1,0 m1,1,1 ...... m1,1,w - 1
......
......
m1,d - 1,0 m1,d - 1,1 ...... m1,d - 1,w - 1
      .
      .
      .
      .
      .
      .
mh - 1,0,0 mh - 1,0,1 ...... mh - 1,0,w - 1
mh - 1,1,0 mh - 1,1,1 ...... mh - 1,1,w - 1
......
......
mh - 1,d - 1,0 mh - 1,d - 1,1 ...... mh - 1,d - 1,w - 1

まずh,d,wの三つの空間の広さのデータが与えられる。

そのあと、地図が与えられる。形式は上記のようである。

"S"がスタート地点で、
"G"がゴール地点である。
"#"が壁であり、進めない。
"."は道であり、移動可能となる。
空間外から移動する変態的な動きはきんもつですよ!
もちろんのことながら"S"や"G"も移動可能である。

出力

始点から終点への最短経路を出力せよ。そのような道がなかった場合は"NA"を出力せよ。

制約

2 ≦ h,d,w ≦ 20

入力例

入力例1

3 3 3
S#.      
#G.
###

.#.
.#.
..#

###
.#.
#..
    

出力例1

10

解説

下にもぐって、二層目の一番下の真ん中で潜る。
そして3層目右真ん中のところから1層目までのぼり、左に行けば最短経路である。

面の間を空白で開けていますが、見やすくしてるだけです。(テストケースはあけて)ないです。

入力例2

3 3 3
S#.      
#G.
###

.#.
.#.
.##

###
.#.
#..
    

出力例1

NA

二層目で三層目にもぐれなくなっちゃったよぉ…いけっこないよ!

思ったこと

テストケースどう作ればよいのだ。

もしかしたらガバガバかも…

一応ランダム生成と全部道とゴールだけ囲うやつとふつーのやつはつくってみました。
テストケース12つだしすくないよねー

もしおかしかったら言っていただければと思います。

実装は簡単だと思う。ただの幅優先だから。

MLE検定です。そんな感じになったらどんな動きをしているか順を追ってみましょう。

気が狂っちゃった☆あはっ!!

出口が見つかんない!って目視でわかるあなたは"NA"だとしても戻しましょう(仕方ないね)

黒歴史を製造することが私の役目であるので、これが世界だ。

参考文献

EDEN パズドラのあのなんか急に世界いってしまうやつ ○○の城○ピュ○のフラッ○ター
高さ 縦 横 英語 どうやらHeight,Depth,Widthならしいですね。
Wizardry *いしのなかにいる* とらうまってこわいね