Maze Escape with Uncertain Traps

You are given a maze game where a single player must escape a labyrinth. The maze is represented by an m x n grid. Each cell in the grid may be:

• .: Plain ground that can be passed.
• #: Wall (impassable).
• A, B, C, …: Trap cells. Each letter represents a type of trap. All cells with the same letter share the same state for the whole game – either all are harmful or all are harmless.
• $: The unique starting position (appears exactly once).
• @: An exit. There may be multiple exit cells (or none).

At the start of the game, the player has H health points. When the player steps on a trap cell:

• If the trap is harmful, 1 health point is lost immediately.
• If the trap is harmless, no health is lost.

The twist is that there are k types of traps (labeled with the first k uppercase letters, e.g. A, B, C, …) and their state (harmful or harmless) is unknown at the beginning. The states are determined by a probability distribution. Each trap type has a binary state: 0 for harmless and 1 for harmful. We denote the trap types as bits in a k-bit number. For example, treat letter A as the 0-th bit (least significant), B as the 1-st bit, C as the 2-nd bit, etc. Hence, every configuration of trap states corresponds to an integer i in the range 0 ≤ i < 2^k.

You are given an array p of size 2^k where p_i is a positive integer. Define
\( S = \sum_{i=0}^{2^k-1} p_i \).
Configuration i occurs with probability \( \frac{p_i}{S} \).

The maze is played as follows: once the trap states are decided at the beginning, the maze becomes deterministic. The player, following an optimal strategy, learns the state of a trap immediately upon stepping on it. The goal is to reach an exit cell while remaining alive. The player dies immediately when his health becomes less than or equal to 0. In other words, the player can afford to trigger at most H - 1 harmful traps along his path.

Task

Given the maze grid, the number of trap types k, the initial health H, and the probability array p, your task is to compute the probability of the player successfully escaping the maze under an optimal strategy.

Notes

• For each trap configuration, the player can compute a route from the starting position to any exit such that the total number of harmful traps encountered is at most H - 1. If such a route exists, the configuration is considered escapable.
• The final answer is the sum of the probabilities of all escapable configurations.
• All formulas must be written in LaTeX format. For example, the probability for a configuration is given by \(\frac{p_{i}}{S}\) where \(S=\sum_{i=0}^{2^k-1}p_i\).

inputFormat

The input is given as follows:

 m n
 k H
 p0 p1 ... p(2^k - 1)
 maze row 1
 maze row 2
 ...
 maze row m

Where:

• m and n are integers representing the dimensions of the grid.
• k is the number of trap types and H is the initial health points.
• The next line contains 2^k positive integers representing the probability array p.
• The following m lines each contain a string of length n representing the maze.

outputFormat

Output a single floating point number which is the probability of escaping the maze under the optimal strategy. It is recommended to print the result with at least 6 decimal places of precision.

sample

3 3
2 1
36 24 24 16
$.@
.#.
...

1.000000