GoThereExactly | Topcoder Archive

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.

Definition

Class:: GoThereExactly
Method:: walk
Parameters:: int, int, int, int, int
Returns:: String
Method signature:: String walk(int r1, int c1, int r2, int c2, int s)
(be sure your method is public)

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.

Examples

```
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"
```
```
18
```
```
16
```
```
16
```
```
13
```
```
5
```
```
Returns: "UULLL"
```

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.