All Submissions


Neo is once again caught up in the machine city. The city is organised in the form of 2D maze and he is situated at one of the cells. Unfortunately, his flying skills are not working. Fire is spreading in the maze and he has very little time to destroy the city. As Neo aspires to destroy the machine city, he has to figure out some way to stay in the city as long as possible in order to fetch sufficient time to do so. In his turn, Neo can either move to his four adjacent cells or stay in his own cell. After his turn, fire propagates in the four adjacent cells from each existing cell which is on fire at that instant.

You will be supplied a maze of size N x M in the form of n strings of size m each. Each cell will be either
'.' → an empty cell
'F' → a cell containing fire
'#' → wall (Neo or fire cannot cross the wall)
'$' → starting position of Neo.
You have to help Neo and find how long he can survive in the maze by giving the maximum number of turns for which he can survive in the city. If he can survive forever your answer would be -1.

Input
First line will give you the value of N and M followed by N strings of M size each describing the maze and the initial positions of fire, wall and Neo. Read until EOF.

Output
A single line giving the maximum number of turns for which Neo can survive in the maze. Print -1 if he can survive forever.

Constraint
The maze will have between 1 to 50 rows and between 2 to 50 characters in each row.
The Number of characters in each row will be same.
There will be exactly one '$' and there will be no other character except '.', '#', '$', 'F'

Sample Input

3 3
F..
.$.
...

5 6
.F#...
F....#
.F###.
F.#.$.
F.#...

7 8
.F....F.
.#.##.#.
.#....#.
F.$##..F
.#....#.
.###.##.
.F....F.


Sample Output

4
-1
4


Problem Setter : Dhruva Bhaswar
Problem Tester: Arjun Singh Bhatia

Languages: Brain,C,C++,Java,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 0 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0