Programming Geek
Rated 4.7/5 based on 1446 reviews

## Jurrasic Park

Problem Description
Smilodon is a ferocious animal which used to live during the Pleistocene epoch (2.5 mya–10,000 years ago). Scientists successfully created few smilodons in an experimental DNA research. A park is established and those smilodons are kept in a cage for visitors.
This park consists of Grasslands(G), Mountains(M) and Waterbodies(W) and it has three gates (situated in grasslands only). Below is a sample layout.

Before opening the park, club authority decides to calculate Safety index of the park. The procedure of the calculation is described below. Please help them to calculate.
Safety Index calculation
Assume a person stands on grassland(x) and a Smilodon escapes from the cage situated on grassland(y). If the person can escape from any of those three gates before the Smilodon able to catch him, then the grassland(x) is called safe else it is unsafe. A person and a Smilodon both take 1 second to move from one area to another adjacent area(top, bottom, left or right) but a person can move only over grasslands though Smilodon can move over grasslands and mountains.
If any grassland is unreachable for Smilodon(maybe it is unreachable for any person also), to increase safe index value Club Authority use to mark those grasslands as safe land. Explained below

For the above layout, there is only one gate at (4,6)
Y is the position of Smilodon’s cage
X is not safe area
Z is a safe area as is it not possible for smilodon to reach z
Safety index=(total grassland areas which are safe*100)/total grassland area

Constraints
3<= R,C <= 10^3
Gates are situated on grasslands only and at the edge of the park
The cage is also situated in grassland only
The position of the cage and the position of three gates are different

Input Format
The first line of the input contains two space-separated integers R and C, denoting the size of the park (R*C)
The second line contains eight space-separated integers where
First two integers represent the position of the first gate
3rd and 4th integers represent the position of second gate
5th and 6th integers represent the position of third gate respectively
The last two integers represent the position of the cage
Next R lines, each contains space separated C number of characters. These R lines represent the park layout.

Output
Safety Index accurate up to two decimal places using Half-up Rounding method

Explanation
Example 1
Input
4 4
1 1 2 1 3 1 1 3
G G G G
G W W M
G G W W
M G M M
Output
75.00
Explanation
 G G G G G W W M G G W W M G M M Mountains 4 Gates- Safe Areas 3 Other Safe Areas 3 Waters 4 Cage Pos.-unsafe 1 Other unsafe areas 1
Safety Index= (6*100)/8
Example 2
Input
4 6
1 6 3 6 4 6 3 4
W M G G G G
M G W G M M
G W G G G G
W G W M W G
Output
69.23