#P3317. [Swerc2008]First Knight

    ID: 2505 传统题 1000ms 128MiB 尝试: 119 已通过: 19 难度: 7 上传者: 标签>难度分类提高+/省选-动态规划期望方程概率与期望首次步分析线性代数与代数高斯消元CF2300WCMG提供SPJ

[Swerc2008]First Knight

题目描述

阿奇博尔德和阿达尔伯特是形影不离的两名骑士。他们偶尔会在户外切磋剑术,比试谁是第一骑士。比试不分胜负,直到两人到达酒馆才结束。

把活动区域划分为 mm 行 nn 列的方格,从左上角 (1,1)(1,1) 开始,到右下角 (m,n)(m,n) 的酒馆结束。两人每一步从当前方格移到一个上下左右相邻的方格。各方向的概率取决于当前位置,例如上坡的方向可能较少被选到。到达一个方格后,下一步按该方格给定的概率选取。

计算两人从 (1,1)(1,1) 第一次到达 (m,n)(m,n) 所需步数的期望。

输入格式

从标准输入读取。输入包含若干组数据。每组第一行是行数 mm 和列数 nn,接下来依次给出四个概率矩阵。每个矩阵有 mm 行,每行 nn 个实数。第 kk 个矩阵中第 ii 行第 jj 列的数 pi,j(k)p_{i,j}^{(k)} 表示从 (i,j)(i,j) 朝下表所列方向移动的概率。

矩阵 方向 到达方格
11 下 (i+1,j)(i+1,j)
22 右 (i,j+1)(i,j+1)
33 上 (i−1,j)(i-1,j)
44 左 (i,j−1)(i,j-1)

移出区域的概率为 00,酒馆方格的四项概率也都是 00。其余每格的四项概率之和为 11,且向下、向右的概率至少有一项大于 00,因此从任意方格出发最终到达酒馆的概率均为 11。

一行 0 0 表示输入结束,这一行没有概率矩阵。

输出格式

向标准输出写入。每组输出一行一个实数,表示所求期望,绝对误差须小于 0.10.1。

样例 1

2 2
0.01 0.50
0.00 0.00
0.99 0.00
0.50 0.00
0.00 0.00
0.50 0.00
0.00 0.50
0.00 0.00
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
3 3
0.000001 0.0 1.0
0.0 1.0 1.0
0.0 0.0 0.0
0.999999 1.0 0.0
1.0 0.0 0.0
0.000001 0.000001 0.0
0.0 0.0 0.0
0.0 0.0 0.0
0.999999 0.0 0.0
0.0 0.0 0.0
0.0 0.0 0.0
0.0 0.999999 0.0
0 0
4.0
41.142857142857146
7.999994000002

数据范围

1≤m,n≤401\le m,n\le40,0≤pi,j(k)≤10\le p_{i,j}^{(k)}\le1。准确的期望值小于 10610^6。