#1307. 2311. 迷宫

2311. 迷宫

#2311. 迷宫

题目描述

小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