[SDOI2011]迷宫探险

题目描述

![](https://cdn.luogu.com.cn/upload/pic/1610.png) ![](https://cdn.luogu.com.cn/upload/pic/1611.png) ![](https://cdn.luogu.com.cn/upload/pic/1612.png) ![](https://cdn.luogu.com.cn/upload/pic/1613.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/pic/1614.png)

输出格式


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

输入输出样例

输入样例 #1

4 3 2 1
.$.
A#B
A#B
.@.
30 30 20 20

输出样例 #1

0.600

输入样例 #2

4 3 2 2
.$.
A#B
A#B
.@.
30 30 20 20

输出样例 #2

0.800

输入样例 #3

4 3 2 3
.$.
A#B
A#B
.@.
30 30 20 20

输出样例 #3

1.000

输入样例 #4

4 3 3 2
.$.
A#B
A#C
@@@
143 37 335 85 95 25 223 57

输出样例 #4

0.858

说明

![](https://cdn.luogu.com.cn/upload/pic/1615.png) ![](https://cdn.luogu.com.cn/upload/pic/1616.png)