Problem F
Shortest Manhattan Distance
Given an $N \times M$ grid, a person at location $(x, y)$ can take a step to the left (decreasing $x$ by 1), right (increasing $x$ by 1), down (decreasing $y$ by 1), or up (increasing $y$ by 1). A path from $(x_0, y_0)$ to $(x_1, y_1)$ is a list of steps ("left", "right", "up", or "down") that starts at $(x_0, y_0)$ and ends at $(x_1, y_1)$. The length of a path is the number of steps in the path. The length of a shortest path between two points is just the Manhattan distance between those two points:
\[ |x_1 - x_0| + |y_1 - y_0| \]Your task will be to find all the shortest paths from $(x_0, y_0)$ to $(x_1, y_1)$.
Input
The input is composed of a single line with four integers, each separated by a single space: $x_0\; y_0\; x_1\; y_1$ (such that $-3 \le x_0, y_0, x_1, y_1 \le 3$)
Output
The output will be the shortest paths between $(x_0, y_0)$ and $(x_1, y_1)$, specified as a list of steps ("left", "right", "up", or "down"), each separated by a single space.
If there is more than one shortest path, then each line will contain a distinct path. The paths can be printed in any order (i.e., for the given sample input, your output doesn’t have to match our output byte-by-byte, but the individual paths must be correct).
If $(x_0, y_0) = (x_1, y_1)$, then print NONE.
| Sample Input 1 | Sample Output 1 |
|---|---|
0 0 1 1 |
right up up right |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 7 5 7 |
NONE |
| Sample Input 3 | Sample Output 3 |
|---|---|
-1 -1 1 1 |
right right up up right up right up right up up right up right right up up right up right up up right right |
