영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
There's a robot in an R × C grid, where some unit squares are blocked so that the robot cannot walk on the square. Now she wants to move to another square, and has asked her owner to program her to do this. This owner happens to be you.
To transfer the code to a robot from your computer requires a lot of energy, so you want to make the program as short as possible - this means using as few commands as possible. As everyone knows, the robot programming language looks as follows:
forwardMove the robot forward a single step in its current direction.rightRotate 90 degrees clockwise.leftRotate 90 degrees counterclockwise.for X { A1 A2 ... An }Repeat the commandsA1,A2, ...,AnX times.call XAdd your current position in the program to the top of the call stack, then jump to the instruction with labelX.returnRemove the last added position from the call stack, and continue execution at the instruction directly after it. In other words, areturnresumes at the line following thecallthat put the position on the stack.gotoblocked XJump to the instruction with labelX, if the robot cannot move forward, i.e. if the square in front of the robot is blocked or lies outside the grid.
A label has the syntax labelname:, and may not contain any whitespaces. A label cannot be inside a loop. The execution starts at the label called main.
Example program
walkandreturn:
for 100 {
forward
}
gotoblocked done
right
right
for 100 {
forward
}
done:
return
main:
for 100 {
call walkandreturn
right
}Note that there is no concept of a function; if the return was not present in walkandreturn, the execution would continue down, running main.
When the robot tries to move towards the edge of the grid, or a blocked square, it doesn't move. When the robot reaches her target square, she wins, even if she doesn't stop on the square.
Input
Input consists of 10 different grids, which you can download from attachments at the bottom of the page. In the results page, the testcases are ordered lexicographically. This means that group 1 is robot_concentric.in, group 2 is robot_cross.in, etc.
Each grid is formatted as follows:
The first line contains the testcase name.
The next line contains two integers R and C (1 ≤ R,C ≤ 1000), the number of rows and columns in the grid.
The following R lines each describe a row of the grid. Each row consists of exactly C squares, each described by one of the following characters:
.free square#blocked squareMgoal square<>^vstart square, indicating the direction of the robot (in the order left, right, up, down).
There is exactly one goal and one start square.
Output
For the given maze, output a valid program on the form described above, that moves the robot from its starting position to the end position.
Additional details
As soon as the robot moves on top of the goal square, the execution is stopped, and you receive an Accepted verdict for said testcase. If you do not reach the goal in 10^8 instructions, you instead get Wrong Answer. Every executed command counts as one instruction, and each iteration of a loop counts as one additional instruction. Labels are free. If execution runs past the last instruction, you get Wrong Answer.
The program is a sequence of tokens separated by whitespace. Any mix of spaces, tabs and line breaks works, and the { and } of a loop are themselves tokens. In a loop for X { ... }, the number of repetitions X must satisfy 1 ≤ X ≤ 10^8.
The call stack may never contain more than 2 · 10^6 positions at the same time. If a call would exceed this, you get Wrong Answer.
If a jump is initiated because of a gotoblocked instruction, the state of every loop is reset.
If a jump is initiated because of a call instruction, the state of every loop is saved on the call stack, and they are then reset. If a return statement is executed, the state of all loops will be set to the saved state on the top of the call stack.
The judges guarantee that there exists a program that attains full score under these constraints.
Submission
To make it easier to submit your solution, a sample submission is provided, which you can download from attachments at the bottom of the page. This submission will get 0 points, but contains valid programs.
Scoring
The scoring is based on the length of your program. The length is the number of times you use one of the listed commands in your program. Our example program has length 11. In particular, labels do not contribute to the length.
If your length on a particular test case is L and the shortest length on this case found by the judges is B, then your score on the testcase is
10 (1 - ((L - B)/L)^2)
Finally, the score per testcase is clamped to the range [0,10].