OpenKattis
University of Chicago

# 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