No.3738 Right Hamiltonian
Problem Statement
There is a maze consisting of an $H \times W$ grid made up of floor cells and wall cells. You are going to explore this maze using a robot.
First, you may choose $1$ floor cell on the grid and place the robot there. You may also choose the robot's initial direction from the four directions: up, down, left, and right.
After that, you may give the robot the following $2$ types of instructions, repeatedly, as many times as you like.
- Go straight: the robot moves $1$ cell forward in the direction it is facing
- Turn right: the robot rotates its direction $90$ degrees clockwise, and then moves $1$ cell forward in the direction it is facing
Note that the robot always moves $1$ cell regardless of which instruction you choose.
Your goal is to make the robot pass through all floor cells (the cells where the robot is at the beginning and at the end are also considered passed through). The robot cannot enter wall cells.
However, if the robot passes through the same floor cell $2$ or more times, the floor of the maze collapses and the robot breaks. The robot also breaks if its destination is a wall cell or outside the grid.
Is it possible to achieve the goal without breaking the robot? If it is possible, find one example of an initial state of the robot and a sequence of instructions that achieves it.
If it is impossible to achieve the goal, output -1.
Constraints
- $1 \leq H, W \leq 2000$
- $S_i$ is a string of length $W$ consisting only of
.and# - There is at least $1$ floor cell
Partial Score
This problem has partial scoring based on subtasks.
| Subtask | Score | Constraints |
|---|---|---|
| 部分点 | 80% (320 pts) | $1 \leq H,\ W \leq 200$ |
| 満点 | 20% (80 pts) | 追加の制約は無い |
Input
The input is given from standard input in the following format.
$H\ W$ $S_1$ $S_2$ $\vdots$ $S_H$
If the $j$-th character of $S_i$ is ., the cell in the $i$-th row from the top and the $j$-th column from the left of the maze is a floor cell; if it is #, the cell is a wall cell.
Output
Output one example of an initial state of the robot and a sequence of instructions that achieves the goal without breaking the robot, in the following format. If none exists, output -1.
$r\ c\ d$ $t$ $X$
The meaning of each variable is as follows.
- $r$ is an integer between $1$ and $H$, inclusive, representing which row from the top of the grid contains the cell where the robot is initially placed
- $c$ is an integer between $1$ and $W$, inclusive, representing which column from the left of the grid contains the cell where the robot is initially placed
- $d$ is a character representing the initial direction of the robot, where
Umeans up,Rmeans right,Dmeans down, andLmeans left - $t$ is an integer between $0$ and $HW-1$, inclusive, representing the number of instructions given to the robot
- $X$ is a string of length $t$ representing the sequence of instructions given to the robot; if the $i$-th instruction is "go straight", the $i$-th character of $X$ is
F, and if it is "turn right", the character isR
Print a newline at the end.
Visualizer
A web-based visualizer for the output is available here.
Please note that sharing visualization results and discussing solutions or observations during the contest are prohibited.
In principle, questions about the visualizer's specifications are not accepted. Please use it only as an auxiliary tool.
Sample
Sample 1
Input
3 4 .... ..#. #...
Output
2 2 L 9 FRRFFRFRF
Let $(i, j)$ denote the cell in the $i$-th row from the top and the $j$-th column from the left.
The robot is initially placed at $(2, 2)$ facing left, and passes through all floor cells along the following path.
$(2, 2) \rightarrow (2, 1) \rightarrow (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 4) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (3, 3) \rightarrow (3, 2)$
Sample 2
Input
2 3 #.. ..#
Output
-1
The robot cannot turn left.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。