题目描述(ID:12275)
标题: 下棋
标签: 搜索 广度优先搜索
详情:
给出一个N×M的被黑白间隔染色的棋盘,其中第i行第j列的格子是白色的当且仅当i+j是偶数。每个格子中都被填入了一个正整数。现在聪聪从棋盘上选出一个矩形,设这个矩形中所有白色格子中的数之积为A,矩形中所有黑色格子中的数之积为B,那么聪聪的得分为S1=A÷B。在计算出聪聪的得分之后,MM也选择一个矩形,并计算出对应的得分S2。若聪聪的得分比MM少则聪聪获胜,否则MM获胜。当然,聪聪希望MM每次都能赢,所以他请你帮忙找出得分最大的矩形。
输入格式:
输入文件first.in包含N+1行。
第1行包含两个正整数N、M,分别表示棋盘的行数和列数。
第2行到N+1行,每行包含M个正整数,其中第i+1行的第j个数表示棋盘上第i行第j列的格子中的数。
输出格式:
输出文件first.out只包含1行,输出最大的得分。因为这个值可能非常大,所以你只需输出答案的前6位。注意不需要对答案进行四舍五入,比如说12.3456789应该被输出为123456。
提示: 实数计算会有误差。为了保证精度,请使用双精度实型(double)来存储所有的实数。
限制: 对于40%的数据,N,M≤25。
对于100%的数据,N,M≤80。
棋盘上每个格子被填入的数都不超过100。
样例:

输入

4 5
4 8 7 9 4
8 3 2 9 7
3 8 4 4 1
6 8 6 9 1

输出

202500

解释

选出左上角为第2行第2列,右下角为第4行第4列的矩形,最大得分为(3×9×4×8×9)÷(2×8×4×6)=20.25,前6位是202500。
登录并解答