Description

Our brilliant yyy once got bored and invented a game that took the world by storm. To commemorate this great invention, he named it “yyy Chess.”

In one scenario, the board looks like this:

ｘｘ．．．ｘｘ
ｘｘ．．．ｘｘ
．．．．．．．
．．．．．．．
．．．．．．．
ｘｘ．．．ｘｘ
ｘｘ．．．ｘｘ

In this case, it is a $7\times7$ board. You can move on ., but not on x. There is only one type of piece, which we denote as Y.

The initial pieces and obstacles are given by the system. Suppose it looks like this:

ｘｘ．．．ｘｘ
ｘｘ．Ｙ．ｘｘ
．．．Ｙ．．．
．．．．．．．
．．．．．．．
ｘｘ．．．ｘｘ
ｘｘ．．．ｘｘ

The rules are simple. Any piece can, and only can, jump over one adjacent piece in the up, down, left, or right direction, moving two squares, and the destination must be empty and not x. After the jump, the jumped-over piece disappears. For example, in the configuration above, we can jump the upper piece downward, after which it becomes:

ｘｘ．．．ｘｘ
ｘｘ．．．ｘｘ
．．．．．．．
．．．Ｙ．．．
．．．．．．．
ｘｘ．．．ｘｘ
ｘｘ．．．ｘｘ

Our goal is to eliminate as many pieces as possible through a sequence of moves, ideally leaving exactly one piece. Since yyy has OCD, he also wants the last piece to stay at the center.

Input Format

All input data yyychess1.in ~ yyychess10.in correspond to $10$ tasks.

For each task:

The first line contains an integer $N$, the size of the board.

For convenience, we define coordinate $(i, j)$ as row $i$, column $j$.

The next line contains a natural number $M$.

• If $M=0$, then

Next comes an $N\times N$ matrix. We use x to denote an unplayable cell, o for an empty playable cell, and y for a cell with a piece. Characters are not separated by spaces.

• If $M>0$, then

Next come $M$ lines, each with two numbers, giving the coordinates of each piece. In this case, there are no obstacle cells.

Output Format

Output several lines, each representing a move.

For each line, output two numbers and one letter. The two numbers represent $(i,j)$, i.e., the coordinate of the piece, and the letter is one of UDLR, representing a jump in the up, down, left, or right direction, respectively.

7
0
xxoooxx
xxoyoxx
oooyooo
ooooooo
ooooooo
xxoooxx
xxoooxx

2 4 D

7
2
2 4
3 4

3 4 U

Hint

Sample Explanation

The two samples describe the same board; the second one simply has no obstacle cells.

With the first sample output, you can score $100\%$.

With the second sample output, you can only score $90\%$, because the final piece is not at the center $(\frac{n+1}{2},\frac{n+1}{2})$.

Scoring Rules

If your answer is valid, and exactly one piece remains at the very center, you score $100\%$ for that testcase.

If your answer is valid, and exactly one piece remains but not at the center, you score $90\%$ for that testcase.

If your answer is valid, and $2$, $3$, or $4$/$5$ pieces remain, you score $80\%$, $60\%$, or $40\%$ for that testcase, respectively.

Otherwise, including having illegal moves or more than $5$ pieces remaining, you score $0$ for that testcase.

The archive provides checker.exe for preliminary use.

Method

Unzip all files, then run on the command line: checker.exe yyychess1.in youranswer.txt youranswer.txt (the last two are your output file; please enter it twice), and it will tell you the result.

Translated by ChatGPT 5