Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem H: 六队-BugZhu寻宝

Problem H: 六队-BugZhu寻宝

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 6  Solved: 1
[Submit][Status][Web Board]

Description

BugZhu一天前往寻宝,他有一张n*m的地图。BugZhu一开始站在(1,1),根据地图宝藏藏在点(n,m),地图显示藏宝的地区施有魔法,BugZhu行动只能向下或者向右移动,当前格子上存在的魔法决定了BugZhu移动的方向。除了左右移动的魔法,藏宝地还有一种飞行的魔法,将会使BugZhu飞到一个指定格子,比如从(I,j)快速移动到(u,v)。通过观察BugZhu分析出每个格子向下和向右移动的机率。BugZhu现在想知道他拿到宝藏的期望移动次数

Input

不超过1000组数据。两个非零整数n,m(n,m<=100)表示地图的大小。接下来n行,每行2*m个小数,表示每个格子向下和向右的概率。一个输入k(k<=100),表示快速移动站的个数,接下来k行,每行4个正整数i,j,u,v(i>=u && j>=v 或者 i<=u && j<=v)。表示格子(i,j)和格子(u,v)联通。

Output

从初始点到达终点的期望移动次数,保留5位小数。

Sample Input

2 2
0.5 0.5 1 0
0 1 0 1
0
2 2
0.5 0.5 1 0
0 1 0 1
1 
1 1 2 2
2 2
0.5 0.5 1 0
0 1 0 1
1 
1 1 1 2

Sample Output

2.00000
1.00000
2.00000

HINT

[Submit][Status][Web Board]