問題一覧 > スコア問題

No.5015 Escape from Labyrinth

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 23
作問者 : platinum / テスター : trineutron
お気に入りにしたユーザー ProblemId : 9273 / 自分の提出
問題文最終更新日: 2023-04-15 00:24:35
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder score contest 4 (順位表) の他の問題:

Story

The player, a wizard, is trying to escape from a labyrinth. To do so, he must pick up the key in the labyrinth and then head for the door.
The labyrinth holds a large number of jewels, and the player intends to collect as many of them as possible before escaping.
However, detectors are installed all over the labyrinth, which severely restrict his actions.
Using his specialties, block generation magic to hide himself and fire magic to destroy detectors, make a splendid escape from the labyrinth!

Problem Statement

The labyrinth is represented by a grid of $\ N\ $ cells vertically and $\ N\ $ cells horizontally. The cells above, below, to the left of, and to the right of a given cell are said to be "adjacent" to it.
The coordinates of the top-left cell are $(0, 0)$, and the coordinates of the cell reached by moving $\ i\ $ cells down and $\ j\ $ cells right from there are $(i, j)$.
The rules of the labyrinth are as follows.

  • Keys, doors, walls, detectors, jewels, and gunpowder are placed in the labyrinth; a cell in which nothing is placed is called an empty cell.
  • The player initially stands on one of the empty cells. The initial value of the player's health is $\ H\ $, and the initial amount of remaining gunpowder is $\ 0\ $.
  • When the player moves to a cell with a key, jewel, or gunpowder, the player automatically obtains the key, jewel, or gunpowder, and that cell becomes an empty cell.
  • Each time the player obtains one jewel, the player earns $\ 10\ $ points.
  • When the player moves to the door cell while holding the key, the escape from the labyrinth is complete.
Each turn, the player can choose one of the following actions. The game starts from turn $\ 1\ $, and health decreases by $\ 1\ $ after the action of every turn.
  • Do nothing.
  • Move to an adjacent cell. However, the player cannot move to a cell containing a wall, a block, or an undestroyed detector, or outside the grid.
  • Place a block on an adjacent empty cell.
  • Destroy a block on an adjacent cell, making it an empty cell. However, walls placed from the beginning cannot be destroyed.
  • Decrease the remaining gunpowder by $\ 1\ $ and fire fire magic in one of the four directions: up, down, left, or right. The flame instantly reaches the edge, but it disappears when it hits a wall, a block, or a detector.
    If it hits a detector, that detector is destroyed and its cell becomes an empty cell.
There are $\ M\ $ detectors in total, and detector $\ i\ $ has an activation interval $\ d_i\ $. When the turn number is a multiple of $\ d_i\ $, the detector activates after the player's action.
If the player is detected by detectors, health decreases by $\ D\ $ per detector.
Each detector detects the cells on the straight lines going up, down, left, and right. If there is a wall, a block, or another detector on a line, it does not detect anything beyond that point.

Output the actions of a player who escapes from the labyrinth without running out of health while obtaining as many jewels as possible.

Score

The total points obtained at the time the escape from the labyrinth is completed is the score for that test case.
However, if health becomes $\ 0\ $ or less before the escape is completed, the verdict is WA and the score for that test case is $\ 0\ $.
If the output is invalid, that test case is judged as WA.
There are $\ 100\ $ test cases in total, and the sum of the scores of all test cases is the score of the submission.
The final ranking is determined by the highest score obtained during the contest, and no system test is performed after the contest ends.
The contest ranking can be viewed from the "Score Order" tab above.

Tools (Visualizer, etc.)

The visualizer and sample code are available on GitHub.
When using the visualizer, you can insert comment lines starting with # into the output.
Since the judge ignores lines starting with #, your submitted program may output comment lines.
You may share screenshots, videos, etc. of any board state of the visualizer on Twitter and elsewhere.
We would appreciate it if you use the following hashtags.

#EscapeFromLabyrinth
#yukicoder
#Siv3D

(Siv3D is the framework used to create this visualizer.)

Input

$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$

  • All input values are integers except for the strings $\ S\ $.
  • The grid size is $\ N = 60\ $ in all test cases.
  • The amount of health lost when the player is detected by a detector satisfies $\ 3 \leq D \leq 7\ $.
  • The player's initial health is $\ H = 1500\ $ in all test cases.
  • The string $\ S_i\ $ represents the information of row $\ i\ $ of the grid. The meaning of each character is as follows, and each of S,G,K appears exactly once.
    • .: empty cell
    • #: wall cell
    • S: initial position of the player
    • G: door cell
    • K: key cell
    • J: jewel cell
    • F: gunpowder cell
    • E: detector cell
  • The number of detectors $\ M\ $ is determined randomly by the generation method described later.
  • The $i\ $-th detector is located at coordinates $(y_i,x_i)$, and its activation interval is $\ d_i\ $. $(0 \leq y_i,x_i \leq N - 1)$
  • The activation intervals of the detectors satisfy $\ 2 \leq d_i \leq 5\ $.

Output

Let the directions up, down, left, and right be U,D,L,R, respectively. On line $i\ $, output the action for turn $\ i\ $.

  • To do nothing, output only S.
  • To move in direction X, output M X, where X is one of U,D,L,R.
  • To generate a block in direction X or destroy the block in direction X, output B X.
  • To fire fire magic in direction X, output F X.

Sample

Sample 1
Input
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
Output
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

Input Generation

Let $\ rand(L,U)\ $ denote a function that generates an integer value between $L\ $ and $\ U\ $, inclusive, uniformly at random.

  • Randomly choose the cells of the player's initial position, the door, and the key. If any of their Manhattan distances is less than $\ 20\ $, choose again.
  • For every cell not yet chosen, make it a wall cell with probability $\ 0.15\ $, a detector cell with probability $\ 0.1\ $, a jewel cell with probability $\ 0.1\ $, and a gunpowder cell with probability $\ 0.02\ $.
  • If escaping from the labyrinth is impossible due to insufficient health or impassability, the generation of the labyrinth is redone from the beginning. (It is guaranteed that escape is possible even without using fire magic.)
  • For each detector, let the activation interval be $\ d=rand(2,5)\ $.
  • In the $i\ $-th test case, let $D=3+(i-1) \% 5\ $.

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