Taco Shortest Path Problem

You are given a rectangular grid representing a field with obstacles, empty cells, a starting cell and a destination cell. Each cell in the grid is represented by one of the following characters:

• . an empty cell that you can move through
• # an obstacle that blocks movement
• S the starting cell
• D the destination cell

You may move in four directions: up, down, left, and right. Your task is to compute the length of the shortest path from the starting cell to the destination cell. If the destination is unreachable, your program should output Unreachable.

The input consists of one or more datasets. Each dataset starts with two integers n and m (the number of rows and columns respectively), followed by n lines each containing m characters forming the grid. The input terminates with a line containing -1.

Note: All formulas in this problem, if any, use LaTeX formatting. In this problem we use plain text for clarity.

inputFormat

The first line of each dataset contains two integers n and m, separated by a space, representing the number of rows and columns of the grid, respectively.

This is followed by n lines, each containing a string of length m where each character is one of {'.', '#', 'S', 'D'}.

The input contains multiple datasets and is terminated by a line containing -1.

Input is provided via standard input (stdin).

outputFormat

For each dataset, output a single line containing the length of the shortest path from the starting cell S to the destination cell D. If the destination is unreachable, output Unreachable.

Output is to be written to standard output (stdout).

## sample

5 5
S....
.....
..#..
.#.#.
....D
-1

8