RotatingBot

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

We had a rectangular grid that consisted of W x H square cells. We placed a robot on one of the cells. The robot then followed the rules given below.

• Initially, the robot is facing east.
• The robot moves in steps. In each step it moves to the adjacent cell in the direction it currently faces.
• The robot may not leave the grid.
• The robot may not visit the same cell twice. (This also means that it may not reenter the starting cell.)
• If a step forward does not cause the robot to break the above rules, the robot takes the step.
• Otherwise, the robot rotates 90 degrees to the left (counter-clockwise) and checks whether a step forward still breaks the above rules. If not, the robot takes the step and continues executing this program (still rotated in the new direction).
• If the rotation left did not help, the robot terminates the execution of this program.
• We can also terminate the execution of the program manually, at any moment.

For example, the following seven images show a series of moves made by the robot in a 12 x 11 board:



We forgot the dimensions of the grid and the original (x,y) coordinates of the cell on which the robot was originally placed, but we do remember its movement. You are given a int[] moves. This sequence of positive integers shall be interpreted as follows: The robot performed moves[0] steps eastwards, turned left, performed moves[1] steps northwards, turned left, and so on. After performing the last sequence of steps, the robot stopped. (Either it detected that it should terminate, or we stopped it manually.) We are not sure if the sequence of moves is valid. If the sequence of moves is impossible, return -1. Else, return the minimum area of a grid in which the sequence of moves is possible. (I.e., the return value is the smallest possible value of the product of W and H.).