You participate in a project to explore an asteroid called Yokohama 2020. A maze-like space in its underground was found by a survey a couple of years ago. The project is to investigate the maze more in detail using an exploration robot.
The shape of the maze was fully grasped by a survey with ground penetrating radars. For planning the exploration, the maze is represented as a grid of cells, where the first cell of the first row is the upper left corner of the grid, and the last cell of the last row is the lower right corner.
Each of the grid cell is either vacant, allowing robot’s moves to it from an adjacent vacant cell, or filled with rocks, obstructing such moves. The entrance of the maze is located in a cell in the uppermost row and the exit is in a cell in the lowermost row.
The exploration robot is controlled by a program stored in it, which consists of sequentially numbered lines, each containing one of the five kinds of commands described below. The register pc specifies the line number of the program to be executed. Each command specifies an action of the robot and a value to be set to pc.
The robot starts at the entrance of the maze facing downwards, and the value of pc is set to 1. The program commands on the lines specified by pc are executed repetitively, one by one, until the robot reaches the exit of the maze.
When the value of pc exceeds the number of lines of the program by its increment, it is reset to 1. The robot stops on reaching the exit cell, which is the goal of the project.
As the capacity of the program store for the robot is quite limited, the number of lines of the program should be minimal. Your job is to develop a program with the fewest possible number of lines among those which eventually lead the robot to the exit.
