#P3603. [Sdoi2014]酗酒者

    ID: 2810 传统题 3000ms 512MiB 尝试: 24 已通过: 3 难度: 9 上传者: 标签>难度分类省选/NOI-概率与期望随机游走首次步分析动态规划期望方程线性代数与代数高斯消元带状矩阵消元CF2700

[Sdoi2014]酗酒者

[SDOI2014] 酗酒者

题目描述

Alice\text{Alice} 发现:人在心情不好的时候,便会选择酗酒。这往往与 OI\text{OI} 选手比赛胜利后的欢腾庆祝不同,酗酒者喝醉后便会忘记回家的路,然后在大街上无规律地乱走乱逛,同时喊着一些谁也听不懂的话。

这几天, Bob\text{Bob} 因为考试的原因心情很不好,每天晚上都会在城里面找一处酒吧。喝醉后离开酒吧开始在城市街道中无规律乱走,直到某一时刻,若他碰巧遇到了在夜晚出来看星星的 Alice\text{Alice} ,便会被她带回家。

已知 Alice\text{Alice} 和 Bob\text{Bob} 所在的城市街道可以被描绘为一个 NN 行 MM 列的格点地图, NN 行依次编号为 00 到 N−1N-1 , MM 列依次编号为 00 到 M−1M-1 。城市中共有 N×MN \times M 处路口,每一个路口可以用坐标 (i,j)(i,j) 表示。若 0≤i<N−10\le i<N-1 ,则 (i,j)(i,j) 与 (i+1,j)(i+1,j) 有无向边,走过这条道路所需时间为 p(i,j)p_{(i,j)}。若 0≤j<M−10\le j<M-1 ,则 (i,j)(i,j) 与 (i,j+1)(i,j+1) 有无向边,走过这条道路所需时间为 q(i,j)q_{(i,j)}。

对于给定的两个点 (u,v)(u,v) 和 (s,t)(s,t) 分别为 Bob\text{Bob} 今晚去的酒吧的位置,和 Alice\text{Alice} 今晚看星星的位置。 Bob\text{Bob} 离开酒吧后,在起点及随后到达的任一路口,若尚未遇见 Alice,他会在与该路口相连的道路中等概率选择一条,沿该道路走向下一个路口。若出发位置与 Alice 所在位置相同,等待时间为 00。在走到下一个路口之前, Bob\text{Bob} 不会回头。同时 Bob\text{Bob} 并不会因为之前走过什么道路而影响之后的行走路线。

具体来说:如果 Bob\text{Bob} 从 (3,4)(3,4) 走到 (3,5)(3,5) ,他有可能在抵达 (3,5)(3,5) 后立刻折回 (3,4)(3,4)。当 N,MN,M 均大于 11 时,对于四叉路口, Bob\text{Bob} 向每一个方向行走的概率都是 1/41/4 ,对于三叉路口(这只存在于城市的边界上)则是 1/31/3 ,对于二叉路口(这只存在于城市的 44 个角落)就是 1/21/2。在单行或单列地图上,同样在实际相邻的道路中等概率选择。

Alice\text{Alice} 希望知道,从 Bob\text{Bob} 离开酒吧, Alice\text{Alice} 期望情况下还需要等多久才能等到 Bob\text{Bob} ,即对于给定的两个点 (u,v)(u,v) 与 (s,t)(s,t),Bob\text{Bob} 从 (u,v)(u,v) 走到 (s,t)(s,t) 的期望用时是多少?

输入格式

第一行 NN , MM 。 之后 N−1N-1 行,每行 MM 个正整数,其中第 i+1i+1 行第 j+1j+1 个为 p(i,j)p_{(i,j)} 。

之后 NN 行,每行 M−1M-1 个正整数,其中第 i+1i+1 行第 j+1j+1 个为 q(i,j)q_{(i,j)} 。 单独一行给出一个整数 QQ ,表示总询问次数。

之后 QQ 行,每行有四个整数 u,v,s,tu,v,s,t。行坐标 u,su,s 的范围为 00 至 N−1N-1,列坐标 v,tv,t 的范围为 00 至 M−1M-1。

输出格式

一共 QQ 行,每一行对应一次询问:从 (u,v)(u,v) 走到 (s,t)(s,t) 的期望时间是多少?每行输出一个实数。正确答案非零时,要求相对误差不超过 0.1%0.1\%。正确答案为零时,现用检查器按绝对误差不超过 10−710^{-7} 判定。

样例 #1

2 2
1 2
3
4
4
0 0 0 1
1 0 0 1
1 1 0 1
0 1 1 0
7.0000
10.0000
8.0000
10.0000

提示

对于 10%10\% 的数据, N×M≤25N \times M \le 25 。

对于 30%30\% 的数据, N×M≤625N \times M \le 625 。

对于 50%50\%的数据, N×M≤2500N \times M \le 2500。

对于 100%100\% 的数据, 1≤N×M≤1041\leq N \times M \le 10^4 , 1≤Q≤1001\leq Q\leq 100 。 ∀i,j\forall i,j , 1≤p(i,j),q(i,j)≤2001\leq p_{(i,j)},q_{(i,j)} \le 200,N,M≥1N,M\geq 1。

此外存在 10%10\% 的数据,min⁡(N,M)≤10\min(N,M) \le 10。