82. Escape

Time Limit: 1 seconds

Memory Limit: 1024 MB

Rating: 900

Problem Statement

In the modified game of snake, the user uses arrow controls to either move the snake one unit up, down, left or right (this is different from the original where the controls are used for changing direction). Snakes like to eat apples, but snakes can eat snakes too. Currently, you are a snake being hunted down by another snake. Hence, you want to escape as far away as possible from your starting position. You start at the origin (0,0). You have a string of instructions consisting of ‘U’, ‘D’, ‘L’, ‘R’ characters which indicate the direction of movement (up, down, left, right). You must use ALL the instructions given in the string. However, you can choose to rearrange the characters in the string. For example, if the string was “ULLD”, you can rearrange the string to “LLDU”, but not “ULL” or “ULDD”. You want to escape as far as possible to increase the chances of your survival. Given a string of instructions, find the maximum distance from the origin you can end up at after using ALL the instructions (and rearranging them if needed). Your answer will be the maximum distance squared so that your answer is an integer. *Note: to avoid confusion, the distance here used is Euclidean distance, not Manhattan distance.

Input

The first line has the string of instructions $S$, the length of which does not exceed $3000$.

Output

Output the answer.

Sample Cases
Sample Input 1:
RRDDL

Sample Output 1:
5


Sample Input 2:
DLRRLDLRLD

Sample Output 2:
10
Explanation

One possible rearrangement is “RLRDD”, which causes the snake to end up in position $(1, -2)$. The square of the distance will be $(1)^2 + (-2)^2 = 5$. Other arrangements such as “LDRDR” are also valid.

Sources

KL Coding Cup March 2023 > Snake > Problem 1

Submit | Back