Wrong Directions
Time limit1sMemory limit128 MB
Given a command string of F, L, and R, count the distinct final positions reachable by changing exactly one character to a different one.
- Level
Medium7 of 10
- Topics
- Simulation, Hash map, Prefix sum, Math
- Solved
- No attempts yet
Problem
Farmer John has a new programmable tractor. To drive it, he types a command string of length () made up only of the characters F, L, and R. An F moves the tractor forward one unit in the direction it currently faces; an L turns it 90 degrees to the left and an R turns it 90 degrees to the right (turning does not change its position). The tractor starts at the origin facing north.
After typing his intended command string, Farmer John realizes he mistyped exactly one character, but he cannot remember which one. A mistyped character is one of the two characters other than the one he intended (for example, where he meant to type R, he might have typed F or L instead). Considering every way that exactly one character could have been mistyped, determine how many distinct final positions the tractor could end up at. The direction it faces at the end does not matter.
Input
A single line containing Farmer John's intended command string (its length is ).
Output
Print a single integer: the number of distinct positions at which the tractor could end up if exactly one character of the command string is mistyped.
Hint
In the sample, Farmer John intended to move forward twice, ending at . Mistyping exactly one character yields four possible strings, FL, FR, LF, and RF, which end at , , , and respectively, for a total of distinct locations.