Maki's Candy Hunt

Candy is scattered across the corridors of Heurika Academy. Maki wants to collect as much candy as possible before getting caught by the tagger.

The corridors form a maze of $N$ rows and $N$ columns. $N$ is an integer between $11$ and $23$ inclusive. Rows are numbered from top to bottom and columns from left to right, each from $1$ to $N$, and the cell in row $x$ and column $y$ is denoted $(x,y)$.

Each cell is either a wall or a passage. The outermost ring of cells is all passage, and Maki and one tagger start on different inner passages. Let $F$ be the number of passages excluding the outermost ring. Then there are $\max(1,\min(F-2,\lfloor 0.2F+0.5\rfloor))$ candies. Initially, the candies are placed on different passages that hold neither Maki nor the tagger, and they may also be placed on the outer passages.

Maki cannot see the whole maze. The direction Maki initially faces is chosen at random from up, down, left, and right, and Maki sees the surroundings as follows.

• On Maki's own cell and straight ahead up to the first wall, Maki sees the terrain, candy, and the tagger. This includes the first wall, and if there is no wall, Maki sees to the edge of the maze.
• For the cells directly to Maki's left, right, and back, Maki only knows whether each is a wall or a passage. For the cells directly to the left and right of each passage cell visible ahead, Maki also knows only the terrain.
• Maki cannot see the cells on either side of the first wall or anything beyond the wall. The view does not bend along passages that branch off to the side either.

Here, left and right are relative to the direction Maki is facing. The figure below shows Maki at $(5,5)$ facing up.

Maki remembers terrain and candy once they have been seen. Maki knows from the start that the outer ring is passage, but has to see it directly to know whether there is candy there. The map given each turn shows the current view and everything remembered so far with the following symbols.

Candy does not move or disappear until Maki eats it. Candy that has been seen stays marked as C even when it is out of view. Cells where only terrain is seen keep their previous candy information. The tagger is shown as H or X only while it is in the current view. . means a known passage, and outside the view it may hold newly placed candy or the tagger. You also cannot tell from # and . alone whether a cell is in the current view.

Maki can also hear the tagger's footsteps. The following value is given based on the shortest distance between the two characters, moving up, down, left, and right without passing through walls. Footsteps do not reveal the tagger's direction.

On each turn, Maki performs one of the following actions. Every action uses one turn.

If the target cell is a wall or outside the maze, only the facing direction changes and Maki does not move. This still uses one turn. O and S do not change the position or the final facing direction.

When Maki performs O, Maki sees the combined view of facing each of the four directions. For cells whose contents are visible from at least one direction, Maki checks candy and the tagger as well, and for all other cells Maki checks only the terrain. What is seen at this point is immediately added to memory. After the tagger moves, only the view in the direction Maki was originally facing is checked again. The next input shows only the tagger visible at that time.

A turn proceeds in the following order.

1. Maki acts. On arriving at a cell with candy, Maki eats it and earns $1$ point.
2. The eaten candy is immediately placed again on another passage that has no Maki, tagger, or other candy. It may also be placed on an outer passage, and the total number of candies stays the same.
3. The view right after Maki's action is added to memory. If Maki and the tagger are on the same cell, Maki is caught and the game ends.
4. The tagger acts once on odd-numbered turns and twice on even-numbered turns. If the two characters are on the same cell right after any of these actions, the game ends immediately.
5. If the game has not ended, Maki's normal view and the footsteps are updated, and play moves on to the next turn.

The tagger also uses moving up, down, left, and right, looking around, and waiting.

The tagger does not eat candy and can stand on a cell with candy. If Maki moves onto a cell that holds both the tagger and candy, Maki earns the point for the candy and is then caught. Since Maki is caught as soon as both are on the same cell, the two characters cannot pass through each other or swap places.

The game ends when Maki is caught or when the tagger's actions on turn $100$ are finished. The score of a game is the number of candies eaten. Points already earned are kept even if Maki is caught.

Design an AI for Maki that avoids the tagger and collects as much candy as possible!

The judge communicates with the player as follows. Values on each line are separated by spaces.

• N is the size of the maze, an integer with $11 \le N \le 23$.
• d is the initial facing direction, one of U, R, D, L.
• a is the footstep level, an integer between $0$ and $3$ inclusive.
• row1 through rowN are the rows of the map. Each line is a string of length $N$, and each character is one of ?, #, ., P, C, H, X. The meaning of each character is the same as in the problem statement.
• remaining_ms is the response time remaining for the game, an integer in milliseconds.
• After every output, print a newline and then flush the buffer.

This is the first turn from a recorded run of the example program.

• CPP20 : main.cpp
• PYTHON3, PYPY3 : main.py