迷宫
时间限制：10s 空间限制：128MB
题目描述
小Z一觉醒来，发现自己在了一个迷宫之中，苦心探索了若干次，却仍然回到了起点。小Z绝望无比，此时，他决定听天由命。
具体来说，这个迷宫有n行m列，小Z现在位于(1,1)，只要走到(n,m)就可以马上离开迷宫。某些格子间有墙而无法通过，迷宫的周围也有一圈墙。而对于可以通过的地方，小Z决定按下述规则移动：在每个格子中，随机选择上下左右四个方向移动，概率由小Z按照自己的方向感确定，当然这个概率会满足下述要求：
1.有墙的方向概率为0。
2.除了(n,m)，每个格子往四个方向的概率加起来等于1。
3.一旦到了(n,m)就马上离开迷宫，故从(n,m)往任意方向的概率均为0。
Your Task
求出小Z离开迷宫的期望步数。
输入格式
第一行n m表示迷宫大小
接下来4个n*m的矩阵，第k个矩阵的第i行第j列的数表示了在格子(i,j)时往k方向移动的概率，k=1为向下(i+1,j)，k=2为向右(i,j+1)，k=3为向上(i-1,j)，k=4为向左(i,j-1)
由(n,m)往任意方向走的概率均为0
输出格式
输出一个数表示答案，保留三位小数
样例输入一
2
样例输入
样例输入一 2 2 0.1 0.1 0 0 0.9 0 0.1 0 0 0 0.9 0 0 0.9 0 0 样例输出一 20.000 样例输入二 1 5 0.0 0.0 0.0 0.0 0.0 1.0 0.1 0.7 0.5 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.9 0.3 0.5 0.0 样例输出二 41.143
样例输出
提示
100%：1≤n,m≤50，迷宫合法，一定可以走到终点，答案不超过10^7
题目来源
没有写明来源