P2489 [SDOI2011] Maze Exploration

https://paste.ubuntu.com/p/H4h73F2h87/

This is a single-player game. At the start of the game, the player’s character spawns at some position in a maze. The player’s goal is to control the character to reach an exit of the maze (there may be multiple exits). There are $k$ types of traps in the maze (denoted by `A`, `B`, `C`, …; the same letter represents the same type of trap). Each type of trap may be harmful or harmless, and at the beginning of the game the player does not know which traps are harmful and which are harmless. Traps of the same type share the same state: all traps marked with the same letter are either all harmful or all harmless; it never happens that some are harmful and others are harmless. Every combination of trap states has a probability. Consider the following example: When $k=2$, there are two types of traps in the maze, denoted by `A` and `B`. There are $4$ combinations of trap states: - `A` is harmless, `B` is harmless. - `A` is harmful, `B` is harmless. - `A` is harmless, `B` is harmful. - `A` is harmful, `B` is harmful. The following table is a valid probability table: | | `A` is harmless | `A` is harmful | | -----------: | -----------: | -----------: | | **`B` is harmless** | $36\%$ | $24\%$ | | **`B` is harmful** | $24\%$ | $16\%$ | When $k=3$, there are $8$ different combinations of trap states. If we still insist on using a probability table, it would be three-dimensional ($2 \times 2 \times 2$, with each dimension corresponding to one trap type). When $k \ge 3$, this makes the problem hard to describe. Therefore, we use an array $p$ of size $2^{k}$ to describe the probability of each case. The index range of $p$ is $0 \sim 2^{k} - 1$. Array $p$ is constructed as follows: For each possible combination of trap states, consider all $k$ types of traps. Let $1$ indicate a harmful trap and $0$ indicate a harmless trap. Treat `A` as the $0$-th bit of a binary number (counting from the right), `B` as the $1$-st bit, `C` as the $2$-nd bit, and so on. With this, we obtain a $k$-bit binary number. After converting it to decimal, the $2^{k}$ combinations of trap states correspond one-to-one to the integers $0 \sim 2^{k} - 1$. Let $S = \displaystyle\sum_{i=0}^{2^k-1} p_i$. Then the probability that trap-state combination $i$ occurs is $\dfrac {p_{i}} {S}$. A valid array $p$ corresponding to the above table is $36, 24, 24, 16$. Of course, the same probability table may correspond to multiple arrays $p$ (in fact, infinitely many arrays $p$ can match the table data). For example, the above table also corresponds to the array $p$: $72, 48, 48, 32$. The player’s character initially has $H$ hit points (HP). When the character steps on a trap, if the trap is harmful, $1$ HP is lost; otherwise, if the trap is harmless, no HP is lost. In either case, the player immediately learns the information of that trap (harmful or harmless). Once HP is less than or equal to $0$, the character dies immediately. The maze can be regarded as an $m \times n$ grid map. Each cell may be: - `.`: flat ground, passable. - `#`: wall, impassable. - `A`, `B`, `C`, …: a trap. - `$`: the starting point; there is exactly one on the map. - `@`: an exit; there may be multiple, or none. The character can move up, down, left, and right. Diagonal movement is not allowed, and the character cannot move outside the map. Given the $m \times n$ map, $k$, $H$, and the probability array of size $2^{k}$, your task is to compute the probability that, under an optimal strategy, the character reaches an exit alive.

The first line contains $4$ integers, denoting $m$, $n$, $k$, and $H$. The next $m$ lines each contain $n$ characters describing the maze map. The last line contains $2^{k}$ nonnegative integers describing the array $p$, with indices starting from $0$.

Output a single number: the probability that, under an optimal strategy, the character reaches an exit alive. Round to $3$ decimal places.

【Sample Explanation 1】 Move right, passing `B`. The probability that `B` is harmful is $\frac {(20+20)}{(30+30+20+20)}=0.4$. If `B` is harmful, the character dies and the game fails; otherwise, the player learns that `B` is harmless and continues through another `B` to reach the exit. The success probability is $0.6$. 【Sample Explanation 2】 Move left, passing `A`. The probability that `A` is harmful is $\frac {(30+30)} {(30+30+20+20)}=0.5$. If `A` is harmful, $1$ HP is lost, then switch to the right path to try `B`. To succeed, `B` must be harmless. Given that `A` is harmful, the conditional probability that `B` is harmless is $\frac {30}{(30+20)}=0.6$. Hence, the probability of this branch is $0.5 \times 0.6 = 0.3$. If `A` is harmless, the player can guide the character through two consecutive `A` to reach the exit, with probability $0.5$. Therefore, the answer is $0.3 + 0.5 = 0.8$. 【Sample Explanation 3】 The character has $3$ HP but needs to pass through at most two traps, so taking either the left or the right path suffices to reach the exit. Constraints | Test point ID | $m$ | $n$ | $k$ | $H$ | | -----------: | -----------: | -----------: | -----------: | -----------: | | $1$ | $29$ | $28$ | $5$ | $1$ | | $2$ | $28$ | $20$ | $4$ | $1$ | | $3$ | $25$ | $30$ | $1$ | $1$ | | $4$ | $25$ | $30$ | $1$ | $2$ | | $5$ | $25$ | $30$ | $1$ | $3$ | | $6$ | $5$ | $5$ | $4$ | $4$ | | $7$ | $12$ | $11$ | $4$ | $5$ | | $8$ | $19$ | $17$ | $5$ | $3$ | | $9$ | $23$ | $25$ | $5$ | $4$ | | $10$ | $30$ | $29$ | $5$ | $5$ | For $100\%$ of the testdata, $1 \le m \le 30$, $1 \le n \le 29$, $k \le 5$, $H \le 5$, $0 \le p_i \le 10^5$, and at least one $p_i \gt 0$. Translated by ChatGPT 5