CodeVita 2018 Round 1 Question: Jurrasic Park

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