GoThereExactly
SRM 834 · 2022-07-25 · by misof
Problem Statement
You are on an infinite grid. You are currently standing on the cell with coordinates (r1, c1). Your goal is to reach the cell with coordinates (r2, c2) in exactly s steps.
In each step you must move from your current cell into one of the four adjacent cells. The moves from (r, c) to (r-1, c) and (r+1, c) are denoted 'U' (up) and 'D' (down). The moves from (r, c) to (r, c-1) and (r, c+1) are denoted 'L' (left) and 'R' (right).
"Reaching the destination in exactly s steps" means that you are NOT allowed to step onto the destination sooner. After each of the earlier steps you must be on some other cell. You can only step on the cell (r2, c2) after making the s-th step. (See Example 2 for an extra clarification of a technical detail.)
If your goal cannot be reached, return "IMPOSSIBLE" (quotes for clarity). Otherwise, return any string of length s that uses the letters 'U', 'D', 'L', 'R' to describe one valid sequence of steps you can take.
Notes
- Remember that the returned sequence must get you from (r1, c1) exactly to (r2, c2) without stepping on (r2, c2) along the way.
- There are no restrictions on how you can move along the grid. In particular, you may move to coordinates that are smaller and/or larger than those where you start and end your walk.
Constraints
- r1, c1, r2 and c2 will all be between 0 and 100, inclusive.
- s will be between 0 and 1,000, inclusive.
4 7 4 7 0 Returns: ""
Going from (4, 7) to (4, 7) in exactly zero steps is easy: just do nothing.
4 7 4 8 42 Returns: "IMPOSSIBLE"
Going from (4, 7) to (4, 8) in exactly 42 steps is impossible: no sequence of exactly 42 'U's, 'D's, 'L's and 'R's will get us there.
4 7 4 7 12 Returns: "UUURRRDDDLLL"
The example return value corresponds to walking along the boundary of a square. Note that this is a valid solution, even though it starts and ends in the same cell. The exact constraint we were given is that after each step except for the last one we must not be in the destination cell. This is true for our solution: after steps 1, 2, ..., 11 we are not on (4, 7), we only return back after step 12.
0 0 4 0 14 Returns: "LLDDRRDRRRDLLL"
0 0 4 4 6 Returns: "IMPOSSIBLE"
Submissions are judged against all 249 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GoThereExactly with a public method string walk(int r1, int c1, int r2, int c2, int s) · 249 test cases · 2 s / 256 MB per case