Robot in a Maze

Interview

Time limit1sMemory limit128 MB

Summary

Find the fewest up, down, left, or right moves from S to any G in each grid maze, or report that no exit exists.

Level: Easy3 of 10
Topics: BFS, Matrix
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Constraints

$1 \le R, C \le 15$

Examples1

Example 1

Input

3
7 8
XXXXXXXX
XSOOXOOX
XOXOOOOX
XOXXXOOX
XOXOXXOX
XOOOXOOX
XXXXXGXX
4 4
XGXX
XSOX
XOOX
XGGX
4 4
XXXX
XSOX
XXXX
XXGX

Expected output

Shortest Path: 11
Shortest Path: 1
No Exit