描述
有一个$n \times m$的二维网格迷宫,需要从$(1,1)$移动到$(n,m)$网格,每次移动可以选择向右和向下移动到相邻的网格。
每个网格都有两个参数$a(i,j),b(i,j)$。
求所有经过网格的$a(i,j)$总和除以$b(i,j)$ 总和的最大值。
输入
第一行两个数字$n,m$。
接着$n$行,每行$2m$个数字,每两个数字表示每个网格的$a(i,j),b(i,j)$。
输出
求所有经过网格的$a(i,j)$总和除以$b(i,j)$ 的最大值。
输出保留4位小数
样例
- 复制
- 复制
- 复制
- 复制
提示
$1 \leq n,m \leq 200$
$1 \leq a(i,j),b(i,j) \leq 10^4$
样例输入如下:

最优路线为(1,1)->(2,1)->(2,2)->(2,3)->(3,3)
$\sum_a = 1+6+4+2+4 =17$
$\sum_b = 2+5+3+1+4 =15$
$17/15≈ 1.1333$

关注我们