21290번 - Robotoptimering 점수다국어

There's a robot in an $N \times M$ 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 have asked her owner to program her to do this. This owner happen to be you.

To transfer the programming 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:

• forward Move the robot forward a single step in its current direction.
• right Rotate $90\deg$ clockwise.
• left Rotate $90\deg$ counterclockwise.
• for X { A1 A2 ... An } Repeat the commands A1, A2, ..., An $X$ times.
• call X Jump to the instruction with label X, and add it to the current position in the call stack.
• return Jump to the last added position in the call stack, and remove it.
• gotoblocked X Jump to the instruction with label X, if the square in front of the robot is blocked.

A label has the syntax labelnamn:, and may only consist of small letters. A label cannot be inside a loop. The execution starts at the label called main.

walkandreturn:
  for 100 {
    forward
  }
  gotoblocked done
  right
  right
  for 100 {
    forward
  }
done:
  return

main:
  for 100 {
    call walkandreturn
    right
  }

Input consists of 10 different grids, which you can download here: robot.zip. Each grid is formatted as follows:

The first line contains the testcase name.

The next line contains two integers $1 \le R \le 1000$ and $1 \le C \le 1000$, the number of rows and columns in the grid.

Each square is one of:

• . free square
• # blocked square
• M goal square
• <>^v start square, indicating the direction of the robot (in the order left, right, up, down).

It should consist of a program on the form described above, that moves the robot from its starting position to the end position.

There are some tools written in Java which you can download here: robot.jar to solve the problem. You can use the command java -cp robot.jar parser.Runner testfall.in < testfall.ans to run the program in the file testfall.ans on the grid in the file testfall.in. The program will tell you if the robot succeeded.

If you also want a graphical representation of the execution, you can run java -cp robot.jar gui.GuiMain.

To submit your solutions, you first run the command java -cp robot.jar gen.Submission, in the folder where your solutions are located. This will generate a Python-file named robot.py. This can be submitted to BOJ (choose the language Python 3).

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 the your program. Our example program has length 11. In particular, labels does not contribute to length.

Assume your length on a test case is $L$, and that the shortest length on this case is $B$. Your score is then

\[ 10 (1 - (\frac{L - B}{L})^2)\]