Asteroid Field

Plot a path through an asteroid field. Given a starting location, a final destination, and a description of the asteroid field, find a shortest path that takes you from the start to the destination without hitting any asteroid.

The asteroid field is described by an $m \times m$ grid of characters, where each character means:

• s: starting location
• d: destination
• -: open space
• *: asteroid

Here is an example of a $4 \times 4$ grid.

s*-*
-*-*
----
*-*d

Your ship can move up, down, left, and right (not diagonally). One move takes the ship one step into an adjacent open cell.

The first line contains a positive integer $n$, the number of data sets. The first line of each data set contains an integer $m$, followed by $m$ lines that each contain $m$ characters. The character s is always in the top-left corner and d is always in the bottom-right corner.

For each data set, print the minimum number of moves needed to reach the destination, or -1 if it is unreachable.