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

 Class: GreedyGlob Method: escapeTime Parameters: String[] Returns: int Method signature: int escapeTime(String[] lab) (be sure your method is public)

Constraints

-lab will contain between 1 and 50 elements, inclusive.
-Each element of lab will contain between 1 and 50 characters, inclusive.
-Each element of lab will contain the same number of characters.
-Each element of lab will contain only the '.', '*', 'S', and 'G' characters.
-Among all elements of lab, there will be exactly one 'S' character and exactly one 'G' character.

Examples

0)

 ```{ "*****", "*S...", "*****", "*.G.*", "*****"}```
`Returns: 4`
 The Glob is sealed in the bottom area, leaving you free to walk out to the right.
1)

 ```{ "**.*", "..G*", "*S.*", "**.*"}```
`Returns: 3`
 You will move one square up, then the Glob will grow vertically (in order to grow by 2 squares instead of 1). Then you'll go left, narrowly escaping the Glob which will now grow horizontally. On your third move, you escape.
2)

 ```{ "*****", "*S...", "*..G*", "*****"}```
`Returns: -1`
 The Glob will grow vertically on its second move, sealing you in forever!

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8000

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10949&pm=8000

jmzero

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Search, Simulation