4637 - 走迷宫 Ⅵ
时间限制 : 1 秒
内存限制 : 128 MB
有一个n×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位小数
样例
输入
3 3 1 2 3 4 5 6 6 5 4 3 2 1 2 2 3 3 4 4
输出
0.8823
输入
5 2 9 1 7 4 6 5 3 2 9 9 7 3 7 9 9 2 6 4 9 4
输出
1.4375
提示
1 \leq n,m \leq 200
1 \leq a(i,j),b(i,j) \leq 10^4
样例输入如下：
最优路线为(1,1)->(1,2)->(1,3)->(2,3)->(3,3)
来源
原创