問題一覧 > 通常問題

No.3738 Right Hamiltonian

レベル : / AI推定難易度 : 3150 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 5
作問者 : 👑 kencho / テスター : uruzunyaa
お気に入りにしたユーザー ProblemId : 13721 / 自分の提出
問題文最終更新日: 2026-11-02 04:29:06
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
グリッド構築24題 (順位表) の他の問題:

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.

SubtaskScoreConstraints
部分点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 U means up, R means right, D means down, and L means 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 is R

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もしくは右上の雲マークをクリックしてアカウントを作成してください。