1041 : [SDOI2011]迷宫探险

这是一个单人游戏。
游戏开始时，玩家控制的人物出生在迷宫的某个位置，玩家的目标是控制人物走到迷宫的某个出口（出口可能有多个）。迷宫里有k类陷阱（用“A”、“B”、“C”……表示，相同字母代表相同类型的陷阱），每类陷阱可能是有害的或无害的，而在游戏开始时玩家并不知道哪些陷阱是有害的，哪些是无害的。同一类陷阱的状态相同，即用同一个字母标志的陷阱要么全部有害，要么全部无害，不会发生一部分有害而另一部分无害的情况。任何陷阱状态的组合都有一个发生概率，考虑下例：
当k=2时，迷宫内共有两类陷阱，分别用“A”和“B”表示，陷阱状态的组合共有4种：
1、“A”是无害陷阱，“B”是无害陷阱。
2、“A”是有害陷阱，“B”是无害陷阱；
3、“A”是无害陷阱，“B”是有害陷阱；
4、“A”是有害陷阱，“B”是有害陷阱；
下面给出了一个合法的概率表格：
 
“A”是无害陷阱
“A”是有害陷阱
“B”是无害陷阱
36%
24%
“B”是有害陷阱
24%
16%
当K=3时，会有8种不同的陷阱状态组合，如果我们依然坚持使用概率表格，那么这个表格将会是三维的（2*2*2，每一维对应着一类陷阱）。当K≥3时，这将使得题目难以描述。因此我们使用一个大小为2k的数组p来描述每种情况发生的可能性，p的下标范围为0~2k-1。
p是这样生成的：
对于每个可能的陷阱状态组合，考虑所有k类陷阱，令1表示某个陷阱有害，0表示某个陷阱无害，把“A”作为二进制数的第0位（从右边开始计数），“B”作为第1位，“C”作为第2位……通过以上操作，我们可以得到一个K位的二进制数，把它转化成十进制后，2k种陷阱状态的组合将会与整数0~2k-1一一对应。
定义S表示P中所有元素和，即：
              
则陷阱状态组合i出现的概率为Pi /S。上述表格对应的一个合法数组P是：
P0 =36
P1 =24
P2 =24
P3=16
 
当然同一个概率表格可能会对应多个数组P（事实上有无数个数组P能够迎合表格数据），例如上述表格同时也对应着下面的数组P：
P0=72
P1=48
P2=48
P3=32
玩家控制的人物初始情况下有H点生命，当人物踏上某个陷阱时，如果这个陷阱是有害的，那么会损失1点生命，否则这个陷阱是无害的，不损失生命。无论上述哪种情况发生，玩家会立刻得到这个陷阱的信息（有害或无害）。一旦生命小于等于0，玩家控制的人物会立刻死亡。
迷宫可以看作m*n的方格地图，每个元素可能是：
“.”：表示这是平地，可以通过；
“#”：表示这是墙，不能通过；
“A”，“B”，“C”……：表示这是一个陷阱；
“$”：表示这是起点，地图中有且仅有一个；
“@”：表示这是终点，地图中可以有多个，也可以一个也没有。
人物可以向上下左右四个方向行走，不可以走对角线，也不可以走出地图。
给定m*n的地图、k、h以及大小为2k的概率数组。你的任务是求出在执行最优策略时，人物能活着走出迷宫的概率。

第一行包含4个整数，分别表示m、n、K、H；
下面m行每行n个字符描述迷宫地图；
最后一行包含2K个非负整数描述数组P，数组下标从0开始。

仅包含一个数字，表示在执行最优策略时，人物活着走出迷宫的概率。四舍五入保留3位小数。

4 3 2 1

.$.

A#B

A#B

.@.

30 30 20 20

0.600

向右边走，经过“B”，“B”为有害陷阱的概率为 (20+20)/(30+30+20+20=)=0.4，若“B”为有害陷阱那么人物就死掉了，游戏失败，否则玩家得知“B”是无害陷阱，继续经过另一个“B”达到终点，胜利的概率为0.6。

概率 动态规划