No.5015 Escape from Labyrinth
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 23
作問者 :
platinum
/ テスター :
trineutron
タグ : / 解いたユーザー数 23
作問者 :
platinum
/ テスター :
trineutron
問題文最終更新日: 2023-04-15 00:24:35
ストーリー
魔法使いであるプレイヤーは迷宮からの脱出を目指している。そのためには迷宮内にある鍵を拾ってから扉へ向かう必要がある。
この迷宮内には大量の宝石があり、プレイヤーは可能な限り宝石を集めてから脱出したいと目論んでいる。
しかし迷宮内には至る所に探知機が設置されており、行動を大きく制限されている。
彼が得意とするブロック生成魔法で身を隠したり火炎魔法で探知機を破壊しながら、見事に迷宮を脱出してみせよ。
問題文
迷宮内の情報は縦$\ N\ $マス、横$\ N\ $マスのグリッドで表される。あるマスに対して上下左右のマスを「隣接している」と表現する。
一番左上のマスの座標を$(0, 0)$とし、そこから下に$\ i\ $マス、右に$\ j\ $マス進んだ先のマスの座標を$(i, j)$とする。
迷宮のルールは以下の通りである。
- 迷宮内には鍵、扉、壁、探知機、宝石、火薬が配置されており、何も配置されていないマスを空のマスと呼ぶ。
- プレイヤーは初めに空のマスのいずれかにいる。体力の初期値は$\ H\ $であり、火薬の残数は$\ 0\ $である。
- プレイヤーが鍵、宝石、火薬のマスに移動した時、自動的に鍵、宝石、火薬を取得し、そのマスは空のマスになる。
- 宝石を一つ取得するたび、プレイヤーは得点を$\ 10\ $獲得する。
- 鍵を取得した状態でプレイヤーが扉のマスに移動した時、迷宮からの脱出が完了となる。
- 何もしない。
- 隣接するマスに移動する。ただし壁、ブロック、破壊されていない探知機があるマスおよびグリッドの外へは移動できない。
- 隣接する空のマスにブロックを設置する。
- 隣接するマスのブロックを破壊し空のマスにする。ただし最初から設置されている壁は破壊できない。
- 火薬の残数を$\ 1\ $減らし、上下左右いずれかの方向に火炎魔法を発射する。火炎は端まで瞬時に到達するが、壁、ブロック、探知機に当たると消滅する。
探知機に当たった場合その探知機は破壊されて空のマスになる。
プレイヤーは探知機に探知された場合、探知機一つあたり体力が$\ D\ $減少する。
各探知機は上下左右の直線上のマスを探知する。直線上に壁、ブロック、他の探知機がある場合、それより先は探知しない。
なるべく多くの宝石を取得しながら、体力が尽きないように迷宮から脱出するプレイヤーの行動を出力せよ。
得点
迷宮からの脱出を完了した時点での、取得した得点の合計値がそのテストケースにおける得点となる。
ただし、脱出が完了する前に体力が$\ 0\ $以下となった場合はWAと判定され、そのテストケースにおける得点は$\ 0\ $となる。
出力が不正であった場合、そのテストケースはWAと判定される。
テストケースは全部で$\ 100\ $個あり、各テストケースの得点の合計が提出の得点となる。
コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。
コンテストの順位は上の「スコア順」タブより確認できる。
ツール（ビジュアライザ等）
ビジュアライザーやサンプルコードをGitHubより入手できます。
ビジュアライザーの利用にあたっては、出力に#から始まるコメント行を挿入できます。
ジャッジは#から始まる行を無視するため、提出プログラムがコメント行を出力しても構いません。
ビジュアライザーの任意の盤面のスクリーンショットや動画等をtwitter等で共有して構いません。
ハッシュタグは以下をご利用いただけると幸いです。
#EscapeFromLabyrinth
#yukicoder
#Siv3D
(Siv3Dは本ビジュアライザーの作成に用いたフレームワークです)
入力
$N\ D\ H$ $S_1$ $S_2$ $\vdots$ $S_N$ $M$ $y_1\ x_1\ d_1$ $y_2\ x_2\ d_2$ $\vdots$ $y_M\ x_M\ d_M$
- 入力は文字列$\ S\ $を除き全て整数である。
- グリッドの大きさは全てのテストケースで$\ N = 60\ $である。
- プレイヤーが探知機に探知された場合の体力の減少値は$\ 3 \leq D \leq 7\ $を満たす。
- プレイヤーの初期体力は全てのテストケースで$\ H = 1500\ $である。
- 文字列$\ S_i\ $はグリッド$\ i\ $行目の情報を表す。各文字の意味は次の通りであり、
S,G,Kはそれぞれただ一つ存在する。.：空のマス#：壁のマスS：プレイヤーの初期位置G：扉のマスK：鍵のマスJ：宝石のマスF：火薬のマスE：探知機のマス
- 探知機の個数$\ M\ $は後述の生成方法によってランダムに決定される。
- $i\ $番目の探知機は座標$(y_i,x_i)$に存在し、作動間隔は$\ d_i\ $である。$(0 \leq y_i,x_i \leq N - 1)$
- 探知機の作動間隔は$\ 2 \leq d_i \leq 5\ $を満たす。
出力
上下左右の方向をそれぞれU,D,L,Rとする。$i\ $行目に$\ i\ $ターン目の行動を出力せよ。
- 何もしない場合は
Sとだけ出力する。 - 方向
Xに移動する場合はMXと出力する。XはU,D,L,Rのいずれかである。 - 方向
Xにブロックを生成、または方向Xのブロックを破壊する場合はBXと出力する。 - 方向
Xに火炎魔法を発射する場合はFXと出力する。
サンプル
サンプル1
入力
60 3 1500 .......JJ....J#..#E#....EE.J..E...E#J.....#.#EE......#..J.J# #E#.....##J..JE....E..#....J.........#......#..#J.........#. .J.J.#.#....J.#..#........J#...#J#.KJE.J.E.#J.#....#......J. J..E..#.E#.......E........JEJ.....F..##..............#...J.J ..J.......JE...#......J.#.#..#J#JFJ.......E..#..#....E.....J #..J.....EE....J........E............##.E#.E.#JJ..........E. ...#......J.J..J#...#...#.#..JE#....##E...#F.#....E....#E#.. .JJ.....###.J.EE...J...#E#E#...E.E.....#E......J..#...#....# E.E.......#JF.J.J.E.##E#...EE..J....F..#.#J#..E#J..E..J...#F ##....F.#F#.E.#.EJ...J#E..#..#.J.......E...J....#..#..#....S .E...E...J..J#........#...E.E.......#.....J..J.....E..E....# .................#J#.....F...JE.#......##.........JJ.J....#. E..J...E##..#.J...#...#.E....##...#.....EEJJJ.##.#.E.....E#. E#.F.#.......JF..#..E#......EJ.....#.#.E.##..JJ.......E.J..E JE..#E....E..E.J#.E...E...J...#J#J.#.E.....E..#E#.E..EF###.. E....J.#..J#....#..EE#.E...E.J.J...E#E#.J..J...E..........J# .....#..J.#JF.#....E..#EE..E..#.......E.........#..J..#..J.F #.EF.......E.J.E............#.........#...........E...#.#J.. F.....JJ...E#..E.#....#.E#...#...F.J.#.E.F.#.....J.....#EJ.E ###......#.E.J.E...#E..#..E...#.....#..#.#......F#.E.J..#.#E ....JEEE..EE.#.E#..#JJ............#J.E.#E..J........E....#.E ..E....EJ...J........#..J..J.#E#.#...#.E....#E.#E.#.#E..#..# ...#E#.E.....#J.E.#.#.J.J...E.JJ#J...#.J...##....J.J.......# .....F....#..J#J..#....#.E...EJ#..#...#.#F#F.EE#..#.....#E.E J#..#....#.#E..#.J.#.#......EJ..J.............#...#....#.E.. ..##EEEE.....JJ..J.#..#..#.E....#J#E#E...E......#JJ#.E..E.#J #E..##..JJ.#.JE.....E.##.E....E#.....#E.#J..#....JJ..#.#.... .E.#.E....#E..E..JEJ..JE..#F#..#.#.#..E#J#......#.E.EJ#..F.E .J....#....J.JE.J#...JF.E..JE.J..#....F.F#..E.##JJE....#F.EE ..F.EJF...E...EE#..J.#F.F#....JE#J.......E#F.....E.....J...# #E##EJ#.E....E......JJ..F##J..E...J..JE..J.EJ..E.....E.EE.#E E#...E...JE.#.#..E..#.J....E..#.#.J#.E.E.#.#E.##.#...#...E.J ...G##..EF.J#J.J....E.F.......E#.J...#..E...##........#.E.#. .....J.#..J...E..EJ..E......J....E...#.#.F#E.EE..#J.E......E ........E.E..#FJ.E#.F..E#.#...........F....J..#.##.##..EFJ.E ....E.#....##.JE...EE.E.#E#..JJEF....#J.#....J.JE..J.....J.. #E...........JJ....###....J#................J..#J.JJ#JE.EJ.. JE.#EJE..#..E..J..#.J.#.....J.J.....#EJJ.E#.E..#E.......E..# #.#J......#....#...#....J.J.E#J.E##.J....EE.#..E..##J..E.... E..E.F.#E....E.....J.#.#.EJ.#.#.J.#...JJ##..#J.....#J.EJ.... .#J.E#......#..E..#..#...J#J....#.E.J......#F.#.E.EJ..E...#. ....J.E..#.#......J...#.JE.#.E...#..E..E.J.E..#.E...#....#EJ ...##.J..J.J...JEJEJ...#.##.#.EE.F...F#.......E.E...#.....J. ...#F..JJ....J##.......F...#..#E....#JJJE.E.J##.E..J...F#J#. #....J..#......EJ.#....EE.#...E....E...#.E.J.E...JEE.E..J..# ...#...#.#....#...E.#.E..E.E..F.E.FEE...............F..#.E#. E.JJ.....E#EJE#....##....#.#.F..#J..#E...#...E.#..##EJ#.#... F....#....#..........E.E.FE.#E......#..#EE..#...#EE....FE..# ..JJ#J..EE...J........J#.E..E..J..E.#...##......J..J........ ..##...#...JJF#J....F....#.....#E.......EJ.........J.#...... ....J.#J.....J....##J..#..JJ.#..#.#.#...J.JE##E.JJ....E#.#.E ...#......EE.....JE..........J.J..J#...#.#..#F..#..J..E...#. E...E..E.F.E#....J....E.#.E.JJ..J.J.J.#.##.....J.E..J....... ##E.....E#EJJ.##.......E.##....EE......E...FE.#.....E.J##..J ..#E#J#......J#......#.#.J....E.#..E..#E.##.#.###......#.... #E#.#J...E.#.JE.#.J...#.....#....J..EE.##EE#..##.......##E.. #.#......#.J.J...E#.E...JE#......#..J.....J#JF..#E.EJ.J..... J....#...JJ...E......#E.J..##.....#.J.#..#E.E..#.....##..J.. E#E.......J#.....EE.J..##...F.....J.FJ#.E........E........#. J.E....J.E.J...E.#..E........##..E....#J..#.#..J...#...E#E.. 374 0 18 5 0 24 5 0 25 2 0 30 3 0 34 2 0 45 3 0 46 4 1 1 3 1 14 5 1 19 2 2 37 5 2 41 5 3 3 3 3 8 4 3 17 3 3 27 3 4 11 2 4 42 4 4 53 2 5 9 4 5 10 2 5 24 3 5 40 5 5 43 2 5 58 5 6 30 2 6 38 5 6 50 5 6 56 5 7 14 2 7 15 5 7 24 5 7 26 4 7 31 5 7 33 4 7 40 3 8 0 5 8 2 5 8 18 5 8 22 3 8 27 3 8 28 5 8 46 2 8 51 5 9 12 3 9 16 3 9 23 5 9 39 4 10 1 5 10 5 2 10 26 5 10 28 3 10 51 4 10 54 3 11 30 2 12 0 4 12 7 4 12 24 4 12 40 5 12 41 4 12 51 5 12 57 4 13 0 4 13 20 2 13 28 2 13 39 4 13 54 2 13 59 5 14 1 5 14 5 4 14 10 4 14 13 5 14 18 2 14 22 4 14 37 2 14 43 4 14 47 4 14 50 2 14 53 3 15 0 3 15 19 3 15 20 4 15 23 2 15 27 3 15 35 2 15 37 3 15 47 5 16 19 4 16 23 2 16 24 5 16 27 2 16 38 5 17 2 5 17 11 4 17 15 5 17 50 3 18 11 5 18 15 3 18 24 3 18 39 5 18 56 4 18 59 5 19 11 5 19 15 5 19 20 2 19 26 4 19 51 4 19 59 4 20 5 4 20 6 4 20 7 4 20 10 3 20 11 4 20 15 4 20 37 5 20 40 4 20 52 2 20 59 3 21 2 2 21 7 3 21 30 5 21 39 3 21 45 3 21 48 2 21 53 4 22 4 4 22 7 2 22 16 4 22 28 2 23 25 3 23 29 2 23 45 4 23 46 5 23 57 4 23 59 4 24 12 3 24 28 5 24 57 2 25 4 2 25 5 3 25 6 4 25 7 2 25 27 4 25 35 5 25 37 3 25 41 3 25 53 3 25 56 4 26 1 5 26 14 2 26 20 3 26 25 3 26 30 3 26 38 5 27 1 2 27 5 4 27 11 2 27 14 3 27 18 2 27 23 2 27 38 3 27 50 2 27 52 2 27 59 5 28 14 2 28 24 5 28 28 2 28 44 3 28 50 3 28 58 4 28 59 3 29 4 2 29 10 5 29 14 4 29 15 2 29 31 3 29 41 3 29 49 4 30 1 4 30 4 3 30 8 2 30 13 5 30 30 3 30 38 4 30 43 3 30 47 3 30 53 3 30 55 3 30 56 2 30 59 2 31 0 5 31 5 3 31 10 2 31 17 5 31 27 4 31 37 2 31 39 3 31 44 4 31 57 4 32 8 3 32 20 3 32 30 5 32 40 2 32 56 5 33 14 3 33 17 4 33 21 3 33 33 3 33 43 4 33 45 3 33 46 4 33 52 5 33 59 5 34 8 4 34 10 4 34 17 2 34 23 5 34 55 5 34 59 5 35 4 2 35 15 3 35 19 5 35 20 2 35 22 5 35 25 2 35 31 5 35 48 2 36 1 4 36 54 3 36 56 2 37 1 5 37 4 2 37 6 3 37 12 4 37 37 5 37 41 5 37 44 2 37 48 2 37 56 2 38 28 2 38 32 3 38 41 5 38 42 5 38 47 5 38 55 2 39 0 4 39 3 2 39 8 2 39 13 5 39 25 3 39 54 3 40 4 2 40 15 3 40 34 4 40 48 5 40 50 4 40 54 4 41 6 4 41 25 4 41 29 4 41 36 5 41 39 4 41 43 4 41 48 4 41 58 4 42 16 2 42 18 3 42 30 5 42 31 4 42 46 2 42 48 2 43 31 2 43 40 2 43 42 2 43 48 5 44 15 4 44 23 3 44 24 5 44 30 2 44 35 2 44 41 5 44 45 4 44 50 2 44 51 3 44 53 3 45 18 3 45 22 5 45 25 5 45 27 2 45 32 3 45 35 4 45 36 2 45 57 4 46 0 4 46 9 5 46 11 2 46 13 4 46 37 3 46 45 3 46 52 2 47 21 2 47 23 4 47 26 2 47 29 5 47 40 2 47 41 3 47 49 3 47 50 4 47 56 5 48 8 3 48 9 2 48 25 5 48 28 4 48 34 2 49 32 5 49 40 5 50 43 2 50 46 5 50 54 5 50 59 3 51 10 4 51 11 3 51 18 2 51 54 4 52 0 4 52 4 4 52 7 3 52 11 2 52 22 2 52 26 2 52 49 3 53 2 3 53 8 4 53 10 2 53 23 4 53 31 3 53 32 3 53 39 4 53 44 2 53 52 2 54 3 3 54 30 4 54 35 4 54 39 4 55 1 3 55 9 5 55 14 4 55 36 2 55 37 5 55 41 4 55 42 2 55 57 3 56 17 5 56 20 3 56 25 3 56 49 4 56 51 4 57 14 2 57 22 2 57 42 5 57 44 3 58 0 2 58 2 4 58 17 2 58 18 4 58 40 2 58 49 4 59 2 4 59 9 4 59 15 3 59 20 3 59 33 2 59 55 5 59 57 2
出力
M L M L M L M L M U M L M L M L M U M L M U M U M L M L M L M L M L M U M U M L M L M L M L M L M L M L M D M L M L M L M L M U M U M L M D M L M L M D M D M D M D M D M L M L M D M D M L M D M L M L M L M L M D M D M D M D M D M D M L M L M L M L M L M L M L M D M D M L M D M D M L M L M L M L M L M L M L M L M L M D M D M D M D M D M L M D M D M D M D M D M L M D M D M L M L M L M U
入力生成方法
$L\ $以上$\ U\ $以下の整数値を一様ランダムに生成する関数を$\ rand(L,U)\ $で表す。
- プレイヤーの初期位置、扉、鍵のマスをランダムに選ぶ。いずれかのマンハッタン距離が$\ 20\ $未満の場合はやり直す。
- まだ選ばれていない全てのマスについて、確率$\ 0.15\ $で壁、確率$\ 0.1\ $で探知機、確率$\ 0.1\ $で宝石、確率$\ 0.02\ $で火薬のマスとする。
- 体力不足または通行不能によって迷宮からの脱出が不可能となった場合、迷宮の生成を最初からやり直す。(火炎魔法を使用しなくても脱出が可能であることが保証される。)
- 各探知機について、作動間隔$\ d=rand(2,5)\ $とする。
- $i\ $番目のテストケースでは、$D=3+(i-1) \% 5\ $とする。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。