Problem Statement

Your mad scientist employer has left you in charge of the lab tonight, and one of her fiendish creations has just escaped its container. The Greedy Glob is a dangerous organism that grows very quickly. You need to escape the lab to get help while avoiding being eaten by the Glob. Luckily, you know the layout of the facility so you can plan your escape route. The layout will be given to you in the elements of lab, and will look something like this:

***.**
*S...*
*..G..
*.....
*.****

'*' characters represent walls you may not pass through while '.' characters are open space. 'S' represents your starting position while the 'G' represents the initial square covered by the Glob. Your goal is to exit the building by moving to a position outside the grid. You get to move first, and on each turn you may move one square North, East, South, or West - or you may remain in the same place.

After each of your moves, the Glob grows. The Glob grows either horizontally or vertically each turn. When the Glob grows vertically, this means that each non-wall square vertically adjacent to a Glob square becomes a Glob square. Similarly, horizontal growth means that all non-wall squares horizontally adjacent to a current Glob square become Glob squares. All squares that were previously Glob squares will also remain covered by Glob. The Glob chooses to grow horizontally or vertically in a greedy manner - it will choose to grow in the direction that will lead to a greater total number of Glob squares at the end of its current turn. If this is a tie, it will grow horizontally. The Glob does not grow beyond the bounds of the grid, and does not count positions outside of the grid when deciding which direction to grow.

You may not enter a Glob square, and if the Glob takes over the square you're on then you are eaten immediately. Return the minimum number of moves required to escape the lab (by leaving the area covered by the grid), or -1 if no escape is possible.

Definition

Constraints

Examples