FriendlyRobot
SRM 682 · 2016-01-04 · by zxqfl
SRM 682 · 2016-01-04 · by zxqfl · Dynamic Programming
Problem Statement
Problem Statement
You are programming a robot which lives on an infinite grid of empty cells. Each cell can be described by two integer coordinates (x, y). The robot always occupies a single cell of the grid. Initially, the robot is at coordinates (0, 0).
A program has already been uploaded into the robot.
The program is a sequence of instructions.
Each instruction is one of the letters U, D, L, or R.
These letters correspond to the commands 'move up', 'move down', 'move left', and 'move right' respectively.
Once the robot is turned on, it will execute each instruction exactly once, in the given order.
After executing all of the instructions, it will stop moving and it will turn itself off.
You are given the robot's current program in the String instructions.
Whenever the robot returns to the cell (0, 0), it claps its hands. You find that funny, so you want to maximize the number of times the robot returns to the cell (0, 0). You are allowed to make at most changesAllowed modifications to the robot's current program. Each modification consists of selecting a single character and changing it to a different character. (The new character still needs to be one of the letters U, D, L, or R. Note that you are not allowed to add or remove characters, you can only change the existing ones.)
Please find and return the maximum number of times the robot can return to the cell (0, 0).
Whenever the robot returns to the cell (0, 0), it claps its hands. You find that funny, so you want to maximize the number of times the robot returns to the cell (0, 0). You are allowed to make at most changesAllowed modifications to the robot's current program. Each modification consists of selecting a single character and changing it to a different character. (The new character still needs to be one of the letters U, D, L, or R. Note that you are not allowed to add or remove characters, you can only change the existing ones.)
Please find and return the maximum number of times the robot can return to the cell (0, 0).
Constraints
- instructions will contain between 2 and 300 characters, inclusive.
- Each character of instructions will be U, D, L, or R.
- changesAllowed will be between 0 and the length of instructions, inclusive.
Examples
0)
"UULRRLLL" 1 Returns: 3
By changing the the first U to a D, you can make the robot return to its starting location 3 times. (Changing the second U to a D is also a valid solution.)
1)
"ULDR" 0 Returns: 1
2)
"ULDR" 2 Returns: 2
3)
"ULDRRLRUDUDLURLUDRUDL" 4 Returns: 8
4)
"LRLDRURDRDUDDDDRLLRUUDURURDRRDRULRDLLDDDDRLRRLLRRDDLRURLRULLLLLRRRDULRULULRLRDLLDDLLRDLUUDUURRULUDUDURULULLDRUDUUURRRURUULRLDLRRRDLLDLRDUULUURUDRURRLURLDLDDUUURRURRLRDLDDULLUDLUDULRDLDUURLUUUURRLRURRDLRRLLLRDRDUUUDRRRDLDRRUUDUDDUDDRLUDDULRURRDRUDLDLLLDLUDDRLURLDUDRUDDDDURLUUUDRLURDDDDLDDRDLUDDLDLURR" 47 Returns: 94
6)
"UD" 1 Returns: 1
Remember that you can change fewer than changesAllowed characters if you wish.
Submissions are judged against all 61 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FriendlyRobot with a public method int findMaximumReturns(string instructions, int changesAllowed) · 61 test cases · 2 s / 256 MB per case