P16990 [NWERC 2018] Game Design

Carol enjoys playing with wooden games. The objective of the game that fascinates her the most is to tilt a maze, made out of $1\text{ cm}$-by-$1\text{ cm}$ blocks, in any of the four cardinal directions to move a ball to a hole in the centre at $(0,0)$. Once the $1\text{ cm}$ wide ball starts moving, it keeps going until either it runs into a wooden block, or it falls into the hole---whichever comes first. Carol is interested in designing a maze of her own, and like any good game designer she already has a fixed solution in mind. This is given as a sequence of tilt moves which must all be followed in order. If any move causes nothing to happen, for example because the ball is up against a block in that direction or already in the hole, the solution does not count. The ball can be placed anywhere to start. Carol will take care of adding a square border of blocks covering the rows and columns $10^9+1$ cells away from the centre in each direction. Design a board which can be won by applying her sequence of moves. :::align{center}  :::

The input consists of: - One line with a string $s$ consisting only of the characters `LRUD` ($1\le |s|\le 20$), the sequence of moves. These characters correspond to the directions $-x,+x,+y,-y$ respectively. No two consecutive characters in $s$ are the same.

If it is possible to create a maze with the given solution, first output $x$ and $y$, the integer coordinates for the ball to start at. Then output $n$, the number of blocks to use, followed by $n$ lines containing the integer coordinates of the blocks. Otherwise, output `impossible`. You may use at most $10^4$ blocks. All coordinates must be at most $10^9$ in absolute value. No coordinate pair may be the same as the centre or any other coordinate pair. If there are multiple valid solutions, you may output any one of them.