### Problem Statement

You have just entered the Colorful Maze. You are given the layout of the maze in the String[] maze, where the j-th character of the i-th element is the cell at row i, column j. The following types of cells exist in the maze:
• '#' - Wall. You cannot enter these cells.
• '.' - Empty cell. You can walk freely into these cells.
• 'A'-'G' - Empty cell with a colored floor. Each of 'A'-'G' represents a different color. You can walk into these cells.
• '\$' - Entrance. This is the cell in which you start.
• '!' - Exit. This is the cell you must reach to finish the maze.

Colored floors with certain colors are dangerous, but you don't know upfront which colors are dangerous. You only know the probability of each color being dangerous. You are given a int[] trap, where the first element is the percent probability of color 'A' being dangerous, the second element is the percent probability of color 'B' being dangerous, and so on. When you step into a cell with a dangerous color, you get damaged by a trap.

When you're inside the maze, you can only move in the four cardinal directions. You cannot move diagonally. Return the probability that you can finish the maze without getting damaged, assuming that you walk according to a strategy that maximizes this probability. See examples for further clarification.

### Definition

 Class: ColorfulMazeTwo Method: getProbability Parameters: String[], int[] Returns: double Method signature: double getProbability(String[] maze, int[] trap) (be sure your method is public)

### Notes

-The returned value must have an absolute or relative error less than 1e-9.

### Constraints

-maze will contain between 1 and 50 elements, inclusive.
-Each element of maze will contain between 1 and 50 characters, inclusive.
-Each element of maze will contain the same number of characters.
-Each character in maze will be one of '#', '.', 'A', 'B', 'C', 'D', 'E', 'F', 'G', '\$', and '!'.
-maze will contain exactly one '\$' and exactly one '!'.
-trap will contain exactly 7 elements.
-Each element of trap will be between 0 and 100, inclusive.

### Examples

0)

 ```{ ".\$.", "A#B", "A#B", ".!." }``` `{ 50, 50, 0, 0, 0, 0, 0 }`
`Returns: 0.5`
 First, go left one cell, and then down one cell into the 'A'. One of two things might happen with equal probability: You get damaged. You fail to finish the maze. You do not get damaged. This means all cells with color 'A' are safe, so you can continue through the 'A' zone and get to the exit. The probability of reaching the exit is 0 (the first case) + 0.5 (the second case) = 0.5. The probability is the same if you go through the 'B' zone.
1)

 ```{ ".\$.", "A#B", "A#B", ".!." }``` `{ 50, 40, 0, 0, 0, 0, 0 }`
`Returns: 0.6`
 As 'B' is safer than it was in the previous example, it is better to go through the 'B' zone.
2)

 ```{ "\$A#", ".#.", "#B!" }``` `{ 10, 10, 10, 10, 10, 10, 10 }`
`Returns: 0.0`
 No matter how you walk, you cannot reach the exit, so you should return 0.
3)

 ```{ "\$A..", "##.A", "..B!" }``` `{ 50, 50, 0, 0, 0, 0, 0 }`
`Returns: 0.5`
4)

 ```{ "\$C..", "##.A", "..B!" }``` `{ 50, 50, 100, 0, 0, 0, 0 }`
`Returns: 0.0`
5)

 `{ ".\$.D.E.F.G.!." }` `{ 10, 20, 30, 40, 50, 60, 70 }`
`Returns: 0.036000000000000004`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14149&pm=10742

lyrically

#### Testers:

PabloGilberto , ivan_metelsky , it4.kp

#### Problem categories:

Dynamic Programming, Graph Theory