Background

This is a submission-based problem where all test data inputs are available for download. Participants need to provide output data. The Luogu evaluation system will score based on the submitted data.

Input data and Windows checker:

http://pan.baidu.com/s/1jHU2UwQ

Linux checker:

http://pan.baidu.com/s/1nv8Yuy1

udp1: All answer files must end with exactly one newline.

Problem Description

Our wise yyy, one day feeling bored, invented (or rather, copied) a game that swept the world. To commemorate this great invention, he named it "yyy Chess" (kkk: Hey! P2361 is already called yyy Chess, what's this?).

In one scenario, the board looks like this:

xx...xx
xx...xx
.......
.......
.......
xx...xx
xx...xx

This is a 7x7 board where '.' indicates a place where a piece can move, and 'x' indicates a place where a piece cannot move. There is only one type of piece, which we'll assume is 'Y'.

The initial pieces and obstacles are predetermined by the system. For example:

xx...xx
xx.Y.xx
...Y...
.......
.......
xx...xx
xx...xx

The rules for moving are simple. Any piece can and can only jump over an adjacent piece (up, down, left, or right) and move two spaces, provided the destination is not occupied and is not an 'x'. After jumping, the jumped piece disappears. For example, from the given board, we can move a piece from above to below, resulting in:

xx...xx
xx...xx
.......
...Y...
.......
xx...xx
xx...xx

The goal is to eliminate as many pieces as possible through a series of moves, ideally leaving only one piece. Due to yyy's obsessive-compulsive disorder, he also wants this final piece to be in the center.

Input Format

All input data files are named yyychess1.in to yyychess10.in, corresponding to 10 tasks.

For each task:

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

For convenience, we define coordinates (i, j) as the i-th row and j-th column.

The next line contains a natural number M.

• If M = 0, then

The following is an NxN matrix sequence. We use 'x' to indicate impassable areas, 'o' to indicate passable but unoccupied areas, and 'y' to indicate occupied areas. Characters are not separated by spaces.

• If M > 0, then

The following are M lines, each containing two numbers, indicating the coordinates of each piece. In this case, there are no obstacle points.

Output Format

Output several lines indicating the moves.

For each line, output two numbers and a letter. The two numbers represent the coordinates (i, j) of the piece, and the letter is one of UDLR, indicating the direction of the jump (up, down, left, or right).

Sample Input and Output

Input Sample #1

7
0
xxoooxx
xxoyoxx
oooyooo
ooooooo
ooooooo
xxoooxx
xxoooxx

Output Sample #1

2 4 D

Input Sample #2

7
2
2 4
3 4

Output Sample #2

3 4 U

Notes

Sample Explanation

Both samples describe the same board, but the second one has no obstacle points.

The output for the first sample can earn 100% of the points.

The output for the second sample can only earn 90% of the points because the final piece is not in the center $(\frac{n+1}{2},\frac{n+1}{2})$.

Scoring Criteria:

• If your answer is valid and there is only one piece left, and it is in the center, you earn 100% of the points.
• If your answer is valid and there is only one piece left, but it is not in the center, you earn 90% of the points.
• If your answer is valid and there are 2, 3, or 4/5 pieces left, you earn 80%, 60%, and 40% of the points, respectively.
• Otherwise, including invalid moves or more than 5 pieces left, you earn no points.

The compressed file provides checker.exe for pre-testing.

Usage:

Extract all files and in the command line, type checker.exe yyychess1.in youranswer.txt youranswer.txt (the last two are your output files, enter them twice)

This will provide you with the results.

见题面 Input 部分

见题面 Output 部分