Robot in a Maze

A robot is stuck in a maze. The maze is a two dimensional grid, and every cell is a wall, an open space the robot can walk on, the robot's starting point, or an exit.

The robot moves one cell at a time, up, down, left, or right. It cannot move diagonally, and it cannot enter a wall. Reaching any exit cell takes the robot out of the maze, and it always starts from the marked point.

Find the smallest number of moves the robot needs to get out of the maze.

The first line has the number of mazes.

Each maze starts with two integers $R$ and $C$. $R$ is the number of rows and $C$ is the number of columns. The next $R$ lines each hold one string describing the cells of that row.

• X is an obstacle the robot cannot pass
• O or 0 is an open space the robot can move into
• S is the robot's starting position
• G is an exit

A maze can have more than one exit.

Print one line per maze, in the order the mazes are given.

If the robot can get out of the maze, print

Shortest Path: t

where $t$ is the length of the shortest path, the smallest number of moves the robot makes.

If there is no way out, print

No Exit

• $1 \le R, C \le 15$